Submission #2125083
Source Code Expand
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int INF = 1e9; const ll LINF = 1e18; /* <url:https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_c> 問題文============================================================ 問題文 ある星には M 種類の言語があり、1[sim]M の番号が付けられています。 この星のある年のCODE FESTIVALには星中から N 人の参加者が集まりました。 i(1≦i≦N) 人目の参加者は Ki 種類の言語 Li,1,Li,2,…,Li,Ki を話すことが出来ます。 ある 2 人は以下のいずれかの条件を満たすときに限り、コミュニケーションを取ることが出来ます。 2 人ともが話すことの出来る言語が存在する。 ある人 X が存在して、 2 人ともが X とコミュニケーションを取ることが出来る。 このとき、N 人すべての参加者が他のすべての参加者とコミュニケーションを取ることが出来るかどうかを判定してください。 制約 2≦N≦105 1≦M≦105 1≦Ki≦M Kiの総和≦105 1≦Li,j≦M Li,1,Li,2,…,Li,Ki は相異なる。 ================================================================= 解説============================================================= UnionFind 問題条件より、結果的に参加者達が全域木のように結ばれればいいということが分かる よってunion Find を用いて、コミュニケーション可能か集団の集合を構築し、 その集合の数によって判定すれば良い ================================================================ */ struct UnionFind { vector<int> data; UnionFind(int size) : data(size, -1) { } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; int main(void) { cin.tie(0); ios::sync_with_stdio(false); ll N,M; cin >> N >> M; vector<vector<ll>> lang(M); for(int i = 0; i < N;i++){ ll K; cin >> K; for(int j = 0; j < K;j++){ ll L; cin >> L; L--; lang[L].push_back(i); } } UnionFind uf(N); for(int i = 0; i < M;i++){ for(int j = 0; j < (int)lang[i].size() - 1;j++){ uf.unionSet(lang[i][j],lang[i][j+1]); } } set<ll> s; for(int i = 0; i < N;i++){ s.insert(uf.root(i)); } if(s.size() == 1){ cout << "YES" << endl; }else{ cout << "NO" << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Interpretation |
User | vjudge4 |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 2929 Byte |
Status | AC |
Exec Time | 24 ms |
Memory | 4736 KB |
Judge Result
Set Name | sample | dataset1 | dataset2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 200 / 200 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt |
dataset1 | sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt |
dataset2 | sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, sample-01.txt, sample-02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 1 ms | 256 KB |
01-02.txt | AC | 1 ms | 256 KB |
01-03.txt | AC | 1 ms | 384 KB |
01-04.txt | AC | 1 ms | 256 KB |
01-05.txt | AC | 1 ms | 256 KB |
01-06.txt | AC | 1 ms | 256 KB |
01-07.txt | AC | 1 ms | 256 KB |
01-08.txt | AC | 1 ms | 256 KB |
01-09.txt | AC | 1 ms | 256 KB |
01-10.txt | AC | 1 ms | 256 KB |
02-01.txt | AC | 19 ms | 4736 KB |
02-02.txt | AC | 16 ms | 1792 KB |
02-03.txt | AC | 19 ms | 3200 KB |
02-04.txt | AC | 22 ms | 4480 KB |
02-05.txt | AC | 20 ms | 2304 KB |
02-06.txt | AC | 24 ms | 4480 KB |
02-07.txt | AC | 20 ms | 2304 KB |
02-08.txt | AC | 14 ms | 1608 KB |
02-09.txt | AC | 17 ms | 3828 KB |
02-10.txt | AC | 15 ms | 3576 KB |
02-11.txt | AC | 16 ms | 3580 KB |
02-12.txt | AC | 17 ms | 3712 KB |
02-13.txt | AC | 17 ms | 3584 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |