CODE FESTIVAL 2016 Final

Submission #11200696

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#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 show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}



struct UnionFind{

	std::vector<int> data;
	// dataの各要素について
	// 負の値:その集合のルートであること示す。また、その絶対値は集合の要素数となっている。
	// 正の値:親ノードの番号(dataのインデックス)。root()を呼び出すたびに集合のルートを指すように書きなおされるので木はそんなに深くならない

	//初期化 size:最大要素数
	UnionFind(int size): data(size, -1) {}
	// 集合を併合する
	// すでに同じ集合だった場合は、falseが返る
	bool unite(int x, int y){
		x=root(x);
		y=root(y);
		if( x != y ){
			// 要素数の大きな方へ合併するためのswap
			if( data[y] < data[x] ) std::swap(x, y);
			// 要素数を加算する
			data[x] += data[y];
			// yの属する集合のルートをxに変更
			data[y] = x;
		}
		return x!=y;
	}
	// 同じ集合かどうか判定
	bool find(int x, int y){
		return root(x) == root(y);
	}

	// 集合の識別番号を返す
	int root(int x){
		// 負の値を持つものがその集合のルート
		// 正の値は同じ集合に属するものを指す(辿ればいずれルートへ着く)
		return (data[x] < 0)? x : data[x]=root(data[x]);
	}
	// 集合の要素数を返す
	int size(int x){
		return -data[ root(x) ];
	}
};

int main()
{
    int n, m;
    cin >> n >> m;

    vector<int> data[m];
    rep(i, n){
        int k; cin >> k;
        rep(j, k){
            int tmp; cin >> tmp; tmp--;
            data[tmp].push_back(i);
        }
    }

    UnionFind uf(n);

    rep(i, m){
        rep(j, data[i].size()-1){
            uf.unite(data[i][j], data[i][j+1]);
        }
    }
    if (uf.size(0) == n) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Submission

Task問題 C - Interpretation
User nameユーザ名 fj_tks
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 400
Source lengthソースコード長 2283 Byte
File nameファイル名
Exec time実行時間 51 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 2 ms 256 KB
01-04.txt AC 1 ms 256 KB
01-05.txt AC 2 ms 256 KB
01-06.txt AC 2 ms 256 KB
01-07.txt AC 2 ms 256 KB
01-08.txt AC 2 ms 256 KB
01-09.txt AC 2 ms 256 KB
01-10.txt AC 2 ms 256 KB
02-01.txt AC 39 ms 4608 KB
02-02.txt AC 40 ms 1152 KB
02-03.txt AC 40 ms 2816 KB
02-04.txt AC 51 ms 4224 KB
02-05.txt AC 44 ms 1536 KB
02-06.txt AC 49 ms 4224 KB
02-07.txt AC 46 ms 1664 KB
02-08.txt AC 33 ms 1124 KB
02-09.txt AC 47 ms 3448 KB
02-10.txt AC 41 ms 3324 KB
02-11.txt AC 41 ms 3324 KB
02-12.txt AC 42 ms 3328 KB
02-13.txt AC 41 ms 3328 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB