Submission #992921
Source Code Expand
import static java.lang.System.in; import static java.lang.System.out; import java.io.*; import java.util.*; public class Main { static final double EPS = 1e-10; static final double INF = 1L << 31; static final double PI = Math.PI; public static Scanner sc = new Scanner(in); StringBuilder sb = new StringBuilder(); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public class UnionFind { private int[] _parent; private int[] _rank; public int find(int i) { int p = _parent[i]; if (i == p) { return i; } return _parent[i] = find(p); } public void union(int i, int j) { int root1 = find(i); int root2 = find(j); if (root2 == root1) return; if (_rank[root1] > _rank[root2]) { _parent[root2] = root1; } else if (_rank[root2] > _rank[root1]) { _parent[root1] = root2; } else { _parent[root2] = root1; _rank[root1]++; } } public UnionFind(int max) { _parent = new int[max]; _rank = new int[max]; for (int i = 0; i < max; i++) { _parent[i] = i; } } } public void run() throws IOException { String input; String[] inputArray; input = br.readLine(); inputArray = input.split(" "); int n = Integer.valueOf(inputArray[0]); int m = Integer.valueOf(inputArray[1]); ArrayList<ArrayList<Integer>> langs = new ArrayList<ArrayList<Integer>>(); for (int i=0; i<m; i++) langs.add(new ArrayList<Integer>()); for (int i=0; i<n; i++){ input = br.readLine(); inputArray = input.split(" "); int k = Integer.valueOf(inputArray[0]); for (int j=1; j<=k; j++){ int l = Integer.valueOf(inputArray[j])-1; langs.get(l).add(i); } } UnionFind U = new UnionFind(n); for (int i=0; i<m; i++){ for (int j=1; j<langs.get(i).size(); j++) U.union(langs.get(i).get(0), langs.get(i).get(j)); } int group = U.find(0); for (int i=1; i<n; i++){ if (U.find(i)!=group){ sb.append("NO"); ln(sb); return; } } sb.append("YES"); ln(sb); } public static void main(String[] args) throws IOException { new Main().run(); } public static void ln(Object obj) { out.println(obj); } }
Submission Info
Submission Time | |
---|---|
Task | C - Interpretation |
User | batchunag |
Language | Java7 (OpenJDK 1.7.0) |
Score | 400 |
Code Size | 2359 Byte |
Status | AC |
Exec Time | 516 ms |
Memory | 37696 KB |
Judge Result
Set Name | sample | dataset1 | dataset2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 200 / 200 | ||||||
Status |
|
|
|
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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 134 ms | 9168 KB |
01-02.txt | AC | 146 ms | 9556 KB |
01-03.txt | AC | 152 ms | 9812 KB |
01-04.txt | AC | 151 ms | 9808 KB |
01-05.txt | AC | 148 ms | 9808 KB |
01-06.txt | AC | 148 ms | 9680 KB |
01-07.txt | AC | 150 ms | 9684 KB |
01-08.txt | AC | 146 ms | 9684 KB |
01-09.txt | AC | 152 ms | 9684 KB |
01-10.txt | AC | 153 ms | 9940 KB |
02-01.txt | AC | 437 ms | 36084 KB |
02-02.txt | AC | 479 ms | 33808 KB |
02-03.txt | AC | 410 ms | 34628 KB |
02-04.txt | AC | 482 ms | 34680 KB |
02-05.txt | AC | 469 ms | 32372 KB |
02-06.txt | AC | 451 ms | 35456 KB |
02-07.txt | AC | 441 ms | 34876 KB |
02-08.txt | AC | 450 ms | 33972 KB |
02-09.txt | AC | 516 ms | 36308 KB |
02-10.txt | AC | 454 ms | 34328 KB |
02-11.txt | AC | 466 ms | 37696 KB |
02-12.txt | AC | 436 ms | 33484 KB |
02-13.txt | AC | 438 ms | 33608 KB |
sample-01.txt | AC | 126 ms | 9044 KB |
sample-02.txt | AC | 128 ms | 8916 KB |