CODE FESTIVAL 2016 Final

Submission #6878041

Source codeソースコード

#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

Task問題 C - Interpretation
User nameユーザ名 kr
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 400
Source lengthソースコード長 1936 Byte
File nameファイル名
Exec time実行時間 46 ms
Memory usageメモリ使用量 2688 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
dataset1 200 / 200 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 200 / 200 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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