CODE FESTIVAL 2016 Final

Submission #5440090

Source codeソースコード

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int m = Integer.parseInt(sa[1]);
		List<List<Integer>> list = new ArrayList<List<Integer>>(n);
		for (int i = 0; i < n; i++) {
			sa = br.readLine().split(" ");
			int k = Integer.parseInt(sa[0]);
			List<Integer> list2 = new ArrayList<Integer>(k);
			for (int j = 1; j <= k; j++) {
				list2.add(Integer.parseInt(sa[j]));
			}
			list.add(list2);
		}
		br.close();

		int[] parent = new int[m + 1];
		for (int i = 0; i < parent.length; i++) {
			parent[i] = i;
		}

		Set<Integer> lang = new HashSet<Integer>();
		for (int i = 0; i < n; i++) {
			List<Integer> list2 = list.get(i);
			lang.add(list2.get(0));
			for (int j = 1; j < list2.size(); j++) {
				union(parent, list2.get(0), list2.get(j));
				lang.add(list2.get(j));
			}
		}

		int a = lang.iterator().next();
		for (int i : lang) {
			if (find(parent, a) != find(parent, i)) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println("YES");
	}

	static void union(int[] parent, int x, int y) {
		int px = find(parent, x);
		int py = find(parent, y);
		if (px != py) {
			parent[px] = py;
		}
	}

	static int find(int[] parent, int x) {
		if (parent[x] == x) {
			return x;
		}
		parent[x] = find(parent, parent[x]);
		return parent[x];
	}
}

Submission

Task問題 C - Interpretation
User nameユーザ名 ks2m
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 400
Source lengthソースコード長 1686 Byte
File nameファイル名
Exec time実行時間 313 ms
Memory usageメモリ使用量 52248 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 69 ms 18772 KB
01-02.txt AC 82 ms 19668 KB
01-03.txt AC 93 ms 17236 KB
01-04.txt AC 98 ms 20308 KB
01-05.txt AC 88 ms 20180 KB
01-06.txt AC 93 ms 18900 KB
01-07.txt AC 89 ms 16980 KB
01-08.txt AC 100 ms 20180 KB
01-09.txt AC 96 ms 18132 KB
01-10.txt AC 102 ms 19668 KB
02-01.txt AC 254 ms 43160 KB
02-02.txt AC 304 ms 49060 KB
02-03.txt AC 218 ms 40976 KB
02-04.txt AC 283 ms 44140 KB
02-05.txt AC 313 ms 45788 KB
02-06.txt AC 294 ms 41700 KB
02-07.txt AC 313 ms 46332 KB
02-08.txt AC 287 ms 43748 KB
02-09.txt AC 304 ms 47992 KB
02-10.txt AC 278 ms 52248 KB
02-11.txt AC 264 ms 50268 KB
02-12.txt AC 300 ms 45340 KB
02-13.txt AC 256 ms 44652 KB
sample-01.txt AC 71 ms 17876 KB
sample-02.txt AC 70 ms 20436 KB