Submission #1986427
Source Code Expand
class UnionFind { private int[] table; private int[] rank; public UnionFind(int size) { this.table = new int[size]; this.rank = new int[size]; for (int i = 0; i < size; i ++) { this.table[i] = i; this.rank[i] = 1; } } public boolean isSame(int node1, int node2) { return find(node1) == find(node2); } public int find(int node) { if (table[node] == node) { return node; } else { return table[node] = find(table[node]); } } public void union(int node1, int node2) { int root1 = find(node1); int root2 = find(node2); if (rank[root1] < rank[root2]) { table[root1] = root2; } else if (rank[root1] > rank[root2]) { table[root2] = root1; } else if (root1 != root2) { table[root2] = root1; rank[root1] ++; } } } public class Main { private static void solve() { int n = ni(); int m = ni(); UnionFind uf = new UnionFind(n + m); for (int i = 0; i < n; i ++) { int k = ni(); for (int j = 0; j < k; j ++) { uf.union(i, n + ni() - 1); } } int root = uf.find(0); for (int i = 0; i < n; i ++) { if (uf.find(i) != root) { System.out.println("NO"); return; } } System.out.println("YES"); } public static void main(String[] args) { new Thread(null, new Runnable() { @Override public void run() { long start = System.currentTimeMillis(); String debug = args.length > 0 ? args[0] : null; if (debug != null) { try { is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug)); } catch (Exception e) { throw new RuntimeException(e); } } reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768); solve(); out.flush(); tr((System.currentTimeMillis() - start) + "ms"); } }, "", 64000000).start(); } private static java.io.InputStream is = System.in; private static java.io.PrintWriter out = new java.io.PrintWriter(System.out); private static java.util.StringTokenizer tokenizer = null; private static java.io.BufferedReader reader; public static String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new java.util.StringTokenizer(reader.readLine()); } catch (Exception e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } private static double nd() { return Double.parseDouble(next()); } private static long nl() { return Long.parseLong(next()); } private static int[] na(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = ni(); return a; } private static char[] ns() { return next().toCharArray(); } private static long[] nal(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nl(); return a; } private static int[][] ntable(int n, int m) { int[][] table = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[i][j] = ni(); } } return table; } private static int[][] nlist(int n, int m) { int[][] table = new int[m][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[j][i] = ni(); } } return table; } private static int ni() { return Integer.parseInt(next()); } private static void tr(Object... o) { if (is != System.in) System.out.println(java.util.Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | C - Interpretation |
User | hiromi_ayase |
Language | Java8 (OpenJDK 1.8.0) |
Score | 400 |
Code Size | 3502 Byte |
Status | AC |
Exec Time | 219 ms |
Memory | 45396 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, sample-01.txt, sample-02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 72 ms | 21460 KB |
01-02.txt | AC | 80 ms | 21132 KB |
01-03.txt | AC | 92 ms | 21716 KB |
01-04.txt | AC | 90 ms | 19796 KB |
01-05.txt | AC | 91 ms | 19924 KB |
01-06.txt | AC | 90 ms | 19796 KB |
01-07.txt | AC | 81 ms | 21844 KB |
01-08.txt | AC | 92 ms | 23892 KB |
01-09.txt | AC | 82 ms | 16468 KB |
01-10.txt | AC | 82 ms | 20564 KB |
02-01.txt | AC | 152 ms | 30652 KB |
02-02.txt | AC | 196 ms | 44452 KB |
02-03.txt | AC | 162 ms | 29024 KB |
02-04.txt | AC | 197 ms | 38764 KB |
02-05.txt | AC | 193 ms | 42284 KB |
02-06.txt | AC | 195 ms | 39224 KB |
02-07.txt | AC | 205 ms | 45396 KB |
02-08.txt | AC | 180 ms | 42520 KB |
02-09.txt | AC | 210 ms | 41364 KB |
02-10.txt | AC | 181 ms | 43244 KB |
02-11.txt | AC | 187 ms | 41340 KB |
02-12.txt | AC | 219 ms | 42220 KB |
02-13.txt | AC | 189 ms | 42552 KB |
sample-01.txt | AC | 71 ms | 19540 KB |
sample-02.txt | AC | 72 ms | 21332 KB |