読者です 読者をやめる 読者になる 読者になる

utsubo’s blog

競技プログラミングとか.

Problem F Gather the Maps!

感想

誰が誰の地図を持っているかsetで持たせました。
とても遅いし、怪しいところあるけど通ればいいよね。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main(void){

	int n;
	while(cin >> n, n !=0){
		vector<vector<int>> ok(n,vector<int>(31));
		bool f = true;
		for(int i=0;i<n;i++){
			int m;cin >> m;
			for(int j=0;j<m;j++){
				int a;cin >> a;
				ok[i][a] = 1;
			}
		}


		vector<set<int>> st(n);
		for(int i=0;i<n;i++)
			st[i].insert(i);

		for(int i=0;i<31;i++){
			vector<int> vec;
			for(int j=0;j<n;j++){
				if(ok[j][i] == 1)vec.push_back(j);
			}

			for(int k=0;k<vec.size();k++){
				for(int j=k+1;j<vec.size();j++){
					st[vec[k]].insert(st[vec[j]].begin(),st[vec[j]].end());
					st[vec[j]].insert(st[vec[k]].begin(),st[vec[k]].end());
				}
			}

			for(int j=0;j<n;j++){
				if(st[j].size() == n){
					cout << i << endl;
					f = false;
					goto END;
				}
			}
		}
		END:
		if(f)cout << -1 << endl;
	}
	return 0;
}

ICPC登録フェイズがきちんと完了できるかがとてつもなく不安です。