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
AC × 2
AC × 12
AC × 25
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