Submission #6878041
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rep1(i,n) for(int i=1;i<=(int)(n);++i) #define rep11(i,n) for(int i=1;i<(int)(n);++i) #define repo(i,o,n) for(int i=o;i<(int)(n);++i) #define repm(i,n) for(int i=(int)(n)-1;i>=0;--i) #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define sperase(v,n) (v).erase(remove(all(v), n), (v).end()) #define vdelete(v) (v).erase(unique(all(v)), (v).end()) #define pb(n) push_back(n) #define mp make_pair #define MOD 1000000007 #define INF LONG_LONG_MAX struct UnionFind { #define MAX 200001 int root[MAX]; void Init() {rep(i,MAX) root[i] = -1;} void unite(int a ,int b) { int a_root = find(a),b_root = find(b); if (a_root != b_root) { if (root[a_root] > root[b_root]) { root[a_root] += root[b_root]; root[b_root] = a_root; } else { root[b_root] += root[a_root]; root[a_root] = b_root; } } } int find(int a) { if (root[a] < 0) return a; else { root[a] = find(root[a]); return root[a]; } } int size(int a) { int a_root = find(a); return -root[a_root]; } /* * root : rootの番号 * unite : 併合 * find : aのrootを返す * size : aのグループの要素数 * */ }; int n,m; UnionFind UF; set<int> st; signed main() { UF.Init(); cin >> n >> m; rep(i,n) { int k; cin >> k; rep(j,k) { int l; cin >> l; UF.unite(i,n+l); } } rep(i,n) st.insert(UF.find(i)); if (st.size() == 1) cout << "YES" << endl; else cout << "NO" << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - Interpretation |
User | kr |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1936 Byte |
Status | AC |
Exec Time | 46 ms |
Memory | 2688 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 | 2 ms | 1792 KB |
01-02.txt | AC | 2 ms | 1792 KB |
01-03.txt | AC | 2 ms | 1792 KB |
01-04.txt | AC | 2 ms | 1792 KB |
01-05.txt | AC | 2 ms | 1792 KB |
01-06.txt | AC | 2 ms | 1792 KB |
01-07.txt | AC | 2 ms | 1792 KB |
01-08.txt | AC | 2 ms | 1792 KB |
01-09.txt | AC | 2 ms | 1792 KB |
01-10.txt | AC | 2 ms | 1792 KB |
02-01.txt | AC | 34 ms | 1792 KB |
02-02.txt | AC | 42 ms | 1792 KB |
02-03.txt | AC | 35 ms | 1792 KB |
02-04.txt | AC | 43 ms | 1792 KB |
02-05.txt | AC | 44 ms | 1792 KB |
02-06.txt | AC | 44 ms | 1792 KB |
02-07.txt | AC | 44 ms | 1792 KB |
02-08.txt | AC | 33 ms | 2304 KB |
02-09.txt | AC | 46 ms | 2688 KB |
02-10.txt | AC | 37 ms | 2304 KB |
02-11.txt | AC | 37 ms | 2304 KB |
02-12.txt | AC | 42 ms | 1792 KB |
02-13.txt | AC | 37 ms | 1792 KB |
sample-01.txt | AC | 2 ms | 1792 KB |
sample-02.txt | AC | 2 ms | 1792 KB |