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; }