Submission #5440090


Source Code Expand

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 Info

Submission Time
Task C - Interpretation
User ks2m
Language Java8 (OpenJDK 1.8.0)
Score 400
Code Size 1686 Byte
Status AC
Exec Time 313 ms
Memory 52248 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 200 / 200
Status
AC × 2
AC × 12
AC × 27
Set Name Test Cases
sample sample-01.txt, sample-02.txt
dataset1 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 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
Case Name Status Exec Time Memory
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