Submission #992129
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
template <typename T>
inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>
inline void chmax(T &l,T r){l=max(l,r);}
typedef vector<int> V;
typedef vector<V> VV;
namespace _DSU{
#define SZ 500000
int mem[2][SZ];
}
class UnionFind{
private:
int *par,*rank;
int find(int x){
if (par[x] == x) return x;
else return par[x] = find(par[x]);
}
public:
UnionFind(int n,int *par,int *rank) :par(par),rank(rank){
for(int i = 0; i < n; i++)par[i] = i,rank[i] = 0;
}
UnionFind(int n):UnionFind(n,_DSU::mem[0],_DSU::mem[1]){}
bool unite(int x, int y){
x = find(x);y = find(y);
if (x == y)return false;
if (rank[x] < rank[y]) par[x] = y;
else{
par[y] = x;
if (rank[x] == rank[y])rank[x]++;
}
return true;
}
bool same(int x, int y){
return find(x) == find(y);
}
};
int main(){
int N,M;
cin>>N>>M;
VV r(M+1);
REP(i,N){
int K;
cin>>K;
REP(j,K){
int L;
cin>>L;
r[L].push_back(i);
}
}
UnionFind uf(N);
for(auto &it:r){
if(it.size()){
for(auto &jt:it){
uf.unite(it.front(),jt);
}
}
}
REP(i,N)if(uf.same(0,i)==false){
cout<<"NO"<<endl;
return 0;
}
cout<<"YES"<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Interpretation |
User |
btk15049 |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
1638 Byte |
Status |
AC |
Exec Time |
28 ms |
Memory |
4608 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 |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
3 ms |
256 KB |
01-02.txt |
AC |
3 ms |
256 KB |
01-03.txt |
AC |
3 ms |
256 KB |
01-04.txt |
AC |
3 ms |
256 KB |
01-05.txt |
AC |
3 ms |
256 KB |
01-06.txt |
AC |
3 ms |
256 KB |
01-07.txt |
AC |
3 ms |
256 KB |
01-08.txt |
AC |
3 ms |
256 KB |
01-09.txt |
AC |
3 ms |
256 KB |
01-10.txt |
AC |
3 ms |
256 KB |
02-01.txt |
AC |
24 ms |
4608 KB |
02-02.txt |
AC |
18 ms |
1664 KB |
02-03.txt |
AC |
22 ms |
2944 KB |
02-04.txt |
AC |
28 ms |
4480 KB |
02-05.txt |
AC |
23 ms |
1920 KB |
02-06.txt |
AC |
28 ms |
4480 KB |
02-07.txt |
AC |
23 ms |
2048 KB |
02-08.txt |
AC |
15 ms |
1508 KB |
02-09.txt |
AC |
21 ms |
3960 KB |
02-10.txt |
AC |
20 ms |
3708 KB |
02-11.txt |
AC |
20 ms |
3580 KB |
02-12.txt |
AC |
21 ms |
3584 KB |
02-13.txt |
AC |
21 ms |
3456 KB |
sample-01.txt |
AC |
3 ms |
256 KB |
sample-02.txt |
AC |
3 ms |
256 KB |