Submission #6878041


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end())
#define vdelete(v) (v).erase(unique(all(v)), (v).end())
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1000000007
#define INF LONG_LONG_MAX

struct UnionFind {
#define MAX 200001
    int root[MAX];
    void Init() {rep(i,MAX) root[i] = -1;}
    void unite(int a ,int b) {
        int a_root = find(a),b_root = find(b);
        if (a_root != b_root) {
            if (root[a_root] > root[b_root]) {
                root[a_root] += root[b_root];
                root[b_root] = a_root;
            } else {
                root[b_root] += root[a_root];
                root[a_root] = b_root;
            }
        }
    }
    int find(int a) {
        if (root[a] < 0) return a;
        else {
            root[a] = find(root[a]);
            return root[a];
        }
    }
    int size(int a) {
        int a_root = find(a);
        return -root[a_root];
    }
    /*
     * root : rootの番号
     * unite : 併合
     * find : aのrootを返す
     * size : aのグループの要素数
     * */
};


int n,m;
UnionFind UF;
set<int> st;


signed main() {
    UF.Init();
    cin >> n >> m;
    rep(i,n) {
        int k;
        cin >> k;
        rep(j,k) {
            int l;
            cin >> l;
            UF.unite(i,n+l);
        }
    }
    rep(i,n) st.insert(UF.find(i));
    if (st.size() == 1) cout << "YES" << endl;
    else cout << "NO" << endl;
}


Submission Info

Submission Time
Task C - Interpretation
User kr
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1936 Byte
Status AC
Exec Time 46 ms
Memory 2688 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 200 / 200
Status
AC × 2
AC × 12
AC × 27
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 2 ms 1792 KB
01-02.txt AC 2 ms 1792 KB
01-03.txt AC 2 ms 1792 KB
01-04.txt AC 2 ms 1792 KB
01-05.txt AC 2 ms 1792 KB
01-06.txt AC 2 ms 1792 KB
01-07.txt AC 2 ms 1792 KB
01-08.txt AC 2 ms 1792 KB
01-09.txt AC 2 ms 1792 KB
01-10.txt AC 2 ms 1792 KB
02-01.txt AC 34 ms 1792 KB
02-02.txt AC 42 ms 1792 KB
02-03.txt AC 35 ms 1792 KB
02-04.txt AC 43 ms 1792 KB
02-05.txt AC 44 ms 1792 KB
02-06.txt AC 44 ms 1792 KB
02-07.txt AC 44 ms 1792 KB
02-08.txt AC 33 ms 2304 KB
02-09.txt AC 46 ms 2688 KB
02-10.txt AC 37 ms 2304 KB
02-11.txt AC 37 ms 2304 KB
02-12.txt AC 42 ms 1792 KB
02-13.txt AC 37 ms 1792 KB
sample-01.txt AC 2 ms 1792 KB
sample-02.txt AC 2 ms 1792 KB