gotutiyan’s blog

競技プログラミングをやったりopenframeworksでお絵かきをしたりしています。

AOJ-ICPC 「君のプライバシーを守れ!」

問題
Save Your Privacy! | Aizu Online Judge

解説
少し入力がめんどくさいのですが、一つずつ流れを追えば大丈夫です。

結局、解答が定まる時は、「各データセットの最後にあるK個ある番号を、全部知っている構成員がただ1人いる時」です。情報を漏らした構成員は1人だけなので、全部知っている人が2人いたらどちらが漏らしたか分からないし、逆に誰も居なければ矛盾したことになります。このような時、−1を出力します。

解法としては、まずは2次元配列vを作って、v[構成員番号][情報を知っている構成員番号] という形で管理します。知っている時1、知らない時0です。例えば、2番目の構成員が3番目の構成員の情報を知っている時、v[1][2]=1 です。0オリジンであることに注意してください。

次にK個のデータを配列ans[ ]に格納すれば、いよいよ見比べる作業に移れます。
各構成員とK個のデータを見比べて、ある構成員が全ての番号について知っていればbool ok がtrueのまま降りてくるので、そのような時countを増やします。ansnumには、答えとなる構成員の番号が入ります。

結局、countが1の時、上記の解答が定まる条件に合致するので、ansnumを出力します。

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
//typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

using namespace std;

int main(){
    int n;
    while(cin>>n &&n){
        vector<vector<int>> v(n,vector<int>(n)); //v[構成員番号][相手の構成員番号]
        rep(i,0,n){
            int x; cin>>x; //最初にデータの個数を読み込み
            rep(j,0,x){ //データをx個受けます
                int num; cin>>num; num--;
                v[i][num]=1;
            }
        }
        int k; cin>>k; //実際に漏洩があった構成員番号を受けます。
        vector<int> ans;
        rep(i,0,k){
            int num; cin>>num; num--;
            ans.pb(num);
        }
        
        int count=0,ansnum=0;
        rep(i,0,n){
            bool ok=true;
            rep(j,0,ans.size()){  
                //i+1番目の構成員について、1つでも情報を知らなければその時点でokはfalseになります。
                if(v[i][ans[j]]!=1)ok=false;
            }
            //okがtrueのまま降りてこれば、i+1番目の構成員は全てを知っていました。情報を漏らすことができます。
            if(ok){
                count++;
                ansnum=i+1;
            }
        }
        if(count==1)cout<<ansnum<<endl;
        else cout<<-1<<endl;
    }
    
    return 0;
}