Submission #993354


Source Code Expand

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
class uft {//union-find tree
public:
    int parent[100000];
    int size[100000];
    int root(int x);
    bool same(int x,int y);
    void unite(int x,int y);
};
int uft::root(int x){
    if(parent[x]==x){
        return x;
    }
    return parent[x] = root(parent[x]);
}
bool uft::same(int x,int y){
    if(root(x)==root(y)){
        return true;
    }else{
        return false;
    }
}
void uft::unite(int x,int y){
    x=root(x);
    y=root(y);
    if(x == y) return;
    parent[x] = y;
    size[y] = size[y]+size[x];
}

int main(){
    int N,M;
    vector<int> v[100001];
    cin>>N>>M;
    for(int i=0;i<N;i++){
        int K;
        cin>>K;
        for(int j=0;j<K;j++){
            int x;
            cin>>x;
            v[x].push_back(i);
        }
    }
    uft u;
    for(int i=0;i<N;i++){
        u.parent[i]=i;
        u.size[i]=1;
    }
    for(int j=1;j<=M;j++){
        if(v[j].size()>1){
            for(int i=1;i<v[j].size();j++){
                u.unite(v[j][0],v[j][i]);
                //cout<<v[j][0]<<' '<<v[j][i]<<endl;
            }
        }
    }
    //cout<<u.size[u.root(0)]<<endl;
    if(u.size[u.root(0)]==N){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    
    
    
    return 0;
}

Submission Info

Submission Time
Task C - Interpretation
User cocococoa
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1457 Byte
Status WA
Exec Time 528 ms
Memory 4736 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 0 / 200 0 / 200
Status
AC × 2
AC × 7
WA × 5
AC × 13
WA × 11
RE × 1
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 5 ms 2560 KB
01-02.txt AC 5 ms 2560 KB
01-03.txt AC 5 ms 2560 KB
01-04.txt WA 5 ms 2560 KB
01-05.txt AC 5 ms 2560 KB
01-06.txt WA 5 ms 2560 KB
01-07.txt WA 5 ms 2560 KB
01-08.txt AC 5 ms 2560 KB
01-09.txt WA 5 ms 2560 KB
01-10.txt WA 5 ms 2560 KB
02-01.txt AC 44 ms 4608 KB
02-02.txt AC 43 ms 3968 KB
02-03.txt AC 43 ms 4096 KB
02-04.txt WA 51 ms 4352 KB
02-05.txt WA 48 ms 3968 KB
02-06.txt RE 528 ms 4352 KB
02-07.txt WA 48 ms 4096 KB
02-08.txt AC 36 ms 3940 KB
02-09.txt WA 50 ms 3832 KB
02-10.txt WA 45 ms 4732 KB
02-11.txt AC 44 ms 4732 KB
02-12.txt WA 44 ms 4736 KB
02-13.txt AC 44 ms 4608 KB
sample-01.txt AC 5 ms 2560 KB
sample-02.txt AC 5 ms 2560 KB