CODE FESTIVAL 2016 Final

Submission #5894001

Source codeソースコード

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

class UnionFind{
    public:
    //親の番号を格納する。親だった場合は-(その集合のサイズ)
    vector<int> parent;

    //-1で初期化
    //最初はすべてバラバラ
    UnionFind(int N){
        parent = vector<int>(N,-1);
    }

    //Aがどのグループに属しているか(Aの根)を調べる
    int root(int A){
        if(parent[A] < 0) return A;
        return parent[A]=root(parent[A]);
    }

    //自分のいるグループの頂点数を調べる
    int size(int A){
        return -parent[root(A)];
    }

    //AとBをくっつける
    bool connect(int A, int B) {
    //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        //既にくっついているからくっつけない
        if(A == B) return false; 

        //大きいほう(A)に小さいほう(B)をくっつける
        //大証が逆ならひっくり返す
        if(size(A) < size(B)) swap(A,B);

        //Aのサイズを更新する
        parent[A] += parent[B];
        //Bの親をAに変更する
        parent[B] = A;

        return true;
    }

    //AとBが同じグループならtrueを返す
    bool same(int A, int B){
        return root(A)==root(B);
    } 
};

int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);

    ll n,m;
    cin>>n>>m;
    ll k;
    vector<vector<int>> v(m);
    for(int i=0;i<n;i++){
        cin>>k;
        for(int j=0;j<k;j++){
            int a;
            cin>>a;
            a--;
            v[a].push_back(i);
        }
    }
    UnionFind uni(n);
    for(int i=0;i<m;i++){
        if(v[i].size()>1){
            int a = v[i][0];
            for(int j=1;j<v[i].size();j++){
                uni.connect(a,v[i][j]);
            }
        }
    }
    for(int i=1;i<n;i++){
        if(!uni.same(0,i)){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;



    

}

Submission

Task問題 C - Interpretation
User nameユーザ名 と と り に ゃ あ
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 400
Source lengthソースコード長 2117 Byte
File nameファイル名
Exec time実行時間 23 ms
Memory usageメモリ使用量 4608 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 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 1 ms 256 KB
01-04.txt AC 1 ms 256 KB
01-05.txt AC 1 ms 256 KB
01-06.txt AC 1 ms 256 KB
01-07.txt AC 1 ms 256 KB
01-08.txt AC 1 ms 256 KB
01-09.txt AC 1 ms 256 KB
01-10.txt AC 1 ms 256 KB
02-01.txt AC 19 ms 4608 KB
02-02.txt AC 15 ms 1280 KB
02-03.txt AC 18 ms 2816 KB
02-04.txt AC 23 ms 4224 KB
02-05.txt AC 20 ms 1664 KB
02-06.txt AC 23 ms 4224 KB
02-07.txt AC 20 ms 1664 KB
02-08.txt AC 13 ms 1124 KB
02-09.txt AC 16 ms 3576 KB
02-10.txt AC 15 ms 3452 KB
02-11.txt AC 15 ms 3452 KB
02-12.txt AC 17 ms 3328 KB
02-13.txt AC 17 ms 3328 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB