Contest Duration: ~ (local time) (180 minutes)

Submission #13478380

Source Code Expand

Copy
```#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
const double PI = acos(-1.0);
#define MOD 1000000007LL
#define endl "\n"

struct UnionFind {
vi par, count;

UnionFind(int N) : par(N), count(N, 1){
for(int i = 0; i < N; i++) par.at(i) = i;
}

int root(int x){
if(par.at(x) == x) return x;
return par.at(x) = root(par.at(x));
}

int unite(int x, int y){
if(root(x) == root(y)) return 0;
if(size(x) < size(y)){
count.at(root(y)) += count.at(root(x));
par.at(root(x)) = root(y);
}
else{
count.at(root(x)) += count.at(root(y));
par.at(root(y)) = root(x);
}
return 1;
}

bool same(int x, int y){
return root(x) == root(y);
}

int size(int x){
return count.at(root(x));
}
};

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll N, M;
cin >> N >> M;
vvll A(M, vll(0));
for(int i = 0; i < N; i++){
ll K;
cin >> K;
for(int j = 0; j < K; j++){
ll L;
cin >> L;
L--;
A.at(L).push_back(i);
}
}
UnionFind uf(N);
for(int i = 0; i < M; i++){
for(int j = 0; j < sz(A.at(i)); j++){
uf.unite(A.at(i).at(0), A.at(i).at(j));
}
}
if(uf.size(0) == N) cout << "YES" << endl;
else cout << "NO" << endl;
}```

#### Submission Info

Submission Time 2020-05-22 20:30:41+0900 C - Interpretation grf C++14 (GCC 5.4.1) 400 1869 Byte AC 26 ms 4736 KB

#### Judge Result

Set Name Score / Max Score Test Cases
sample 0 / 0 sample-01.txt, sample-02.txt
dataset1 200 / 200 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 200 / 200 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 1 ms 256 KB
01-02.txt 1 ms 256 KB
01-03.txt 1 ms 256 KB
01-04.txt 1 ms 256 KB
01-05.txt 1 ms 256 KB
01-06.txt 1 ms 256 KB
01-07.txt 1 ms 256 KB
01-08.txt 1 ms 256 KB
01-09.txt 1 ms 256 KB
01-10.txt 1 ms 256 KB
02-01.txt 22 ms 4736 KB
02-02.txt 17 ms 2176 KB
02-03.txt 19 ms 3200 KB
02-04.txt 26 ms 4736 KB
02-05.txt 21 ms 2560 KB
02-06.txt 24 ms 4736 KB
02-07.txt 22 ms 2560 KB
02-08.txt 15 ms 1992 KB
02-09.txt 18 ms 4212 KB
02-10.txt 16 ms 3832 KB
02-11.txt 16 ms 3832 KB
02-12.txt 18 ms 3840 KB
02-13.txt 18 ms 3712 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB