Submission #11610636
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
//グリッド:(典型)dp,dfs,bfs,最短経路,その他
struct UnionFind{
vector<int> par,depth,Size;
UnionFind(int n){
par.resize(n); depth.resize(n); Size.resize(n);
for(int i=0; i<n; i++){
par[i]=i;
depth[i]=0;
Size[i]=1;
}
}
int find(int x){
if(par[x]==x){
return x;
}
else{
return par[x]=find(par[x]);
}
}
bool same(int x, int y){
return find(x)==find(y);
}
void unite(int x, int y){
x=find(x); y=find(y);
if(x==y) return;
if(depth[x]<depth[y]) swap(x,y);
if(depth[x]==depth[y]) depth[x]++;
par[y]=x;
Size[x]+=Size[y];
}
int size(int x){
return Size[find(x)];
}
};
int main(){
ll n,m;cin>>n>>m;
UnionFind uf(220000);
rep(i,n){
ll k;cin>>k;
rep(j,k){
ll l;cin>>l;
if(!uf.same(i+1,l+n)){
//cout<<i+1<<" "<<l+n<<endl;
uf.unite(i+1,l+n);
}
}
}
bool ok=true;
rrep(i,n){
if(!uf.same(1,n)) ok=false;
}
if(ok) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Interpretation |
User |
NrKm |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1796 Byte |
Status |
WA |
Exec Time |
47 ms |
Memory |
2816 KB |
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
0 / 200 |
0 / 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 |
3 ms |
2816 KB |
01-02.txt |
AC |
3 ms |
2816 KB |
01-03.txt |
AC |
3 ms |
2816 KB |
01-04.txt |
AC |
3 ms |
2816 KB |
01-05.txt |
AC |
3 ms |
2816 KB |
01-06.txt |
AC |
3 ms |
2816 KB |
01-07.txt |
AC |
3 ms |
2816 KB |
01-08.txt |
WA |
3 ms |
2816 KB |
01-09.txt |
AC |
3 ms |
2816 KB |
01-10.txt |
AC |
3 ms |
2816 KB |
02-01.txt |
AC |
34 ms |
2816 KB |
02-02.txt |
WA |
39 ms |
2816 KB |
02-03.txt |
WA |
33 ms |
2816 KB |
02-04.txt |
AC |
43 ms |
2816 KB |
02-05.txt |
AC |
41 ms |
2816 KB |
02-06.txt |
WA |
42 ms |
2816 KB |
02-07.txt |
AC |
42 ms |
2816 KB |
02-08.txt |
WA |
33 ms |
2816 KB |
02-09.txt |
AC |
47 ms |
2816 KB |
02-10.txt |
AC |
38 ms |
2816 KB |
02-11.txt |
WA |
39 ms |
2816 KB |
02-12.txt |
AC |
37 ms |
2816 KB |
02-13.txt |
WA |
38 ms |
2816 KB |
sample-01.txt |
AC |
3 ms |
2816 KB |
sample-02.txt |
AC |
3 ms |
2816 KB |