CODE FESTIVAL 2016 Final

Submission #6771437

Source codeソースコード

//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <iostream>
#include <limits>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;

struct UnionFind {
	vector<size_t> parent;
	vector<size_t> rank;
	size_t find_parent(size_t x) {
		if (parent[x] == x) {
			return x;
		} else {
			parent[x] = find_parent(parent[x]);
			return parent[x];
		}
	}
	explicit UnionFind(size_t size) {
		parent.resize(size);
		rank.resize(size);
		for (size_t i = 0; i < size; i++) {
			parent[i] = i;
			rank[i] = 0;
		}
	}
	virtual ~UnionFind() {}
	void unite(size_t x, size_t y) {
		size_t px = find_parent(x);
		size_t py = find_parent(y);
		if (px == py) {
			return;
		}
		if (rank[px] < rank[py]) {
			parent[px] = py;
		} else if (rank[px] > rank[py]) {
			parent[py] = px;
		} else {	// rank[px] == rank[py]
			parent[py] = px;
			rank[px]++;
		}
	}
	bool is_same(size_t x, size_t y) {
		return find_parent(x) == find_parent(y);
	}
	unordered_map<size_t, set<size_t>> create_map_parent_to_elements() {
		unordered_map<size_t, set<size_t>> ans;
		for (size_t i = 0; i < parent.size(); i++) {
			ans[find_parent(i)].insert(i);
		}
		return ans;
	}
};

int main() {
     int N, M;
     cin >> N >> M;
     UnionFind uf(N + M);
     for (int i = 0; i < N; i++) {
     	int Ki;
     	cin >> Ki;
     	for (int j = 0; j < Ki; j++) {
     		 int Lj;
     		 cin >> Lj;
     		 Lj--;
     		 uf.unite(i, N + Lj);
     	}
     }
     for (int i = 0; i < N; i++) {
     	if (!uf.is_same(0, i)) {
     		cout << "NO" << endl;
     		return 0;
     	}
     }
     cout << "YES" << endl;
}  

Submission

Task問題 C - Interpretation
User nameユーザ名 tttmmm
Created time投稿日時
Language言語 C++14 (Clang 3.8.0)
Status状態 AC
Score得点 400
Source lengthソースコード長 1991 Byte
File nameファイル名
Exec time実行時間 126 ms
Memory usageメモリ使用量 3328 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 2 ms 256 KB
01-03.txt AC 2 ms 256 KB
01-04.txt AC 2 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 85 ms 1920 KB
02-02.txt AC 110 ms 1792 KB
02-03.txt AC 88 ms 1152 KB
02-04.txt AC 111 ms 2688 KB
02-05.txt AC 112 ms 1664 KB
02-06.txt AC 110 ms 2688 KB
02-07.txt AC 117 ms 1792 KB
02-08.txt AC 93 ms 1792 KB
02-09.txt AC 126 ms 3328 KB
02-10.txt AC 101 ms 1792 KB
02-11.txt AC 101 ms 1792 KB
02-12.txt AC 100 ms 1792 KB
02-13.txt AC 99 ms 1792 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB