Submission #992244
Source Code Expand
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.StringTokenizer; public class Main { static BufferedReader in; static PrintWriter out; static StringTokenizer tok; void solve() throws IOException { int n = ni(); int m = ni(); ArrayList<ArrayList<Integer>> list = new ArrayList<>(); for (int i = 0; i < m; i++) { list.add(new ArrayList<>()); } for (int i = 0; i < n; i++) { int k = ni(); for (int j = 0; j < k; j++) { int l = ni() - 1; list.get(l).add(i); } } UnionFind uf = new UnionFind(n); for (int i = 0; i < m; i++) { for (int j = 1; j < list.get(i).size(); j++) { uf.union(list.get(i).get(0), list.get(i).get(j)); } } out.println(uf.size(0) == n ? "YES" : "NO"); } class UnionFind { private int[] parent; public UnionFind(int size) { parent = new int[size]; Arrays.fill(parent, -1); } public boolean union(int x,int y) { x = root(x); y = root(y); if (x!=y) { if (parent[y] < parent[x]) { int tmp = y; y = x; x = tmp; } parent[x] += parent[y]; parent[y] = x; return true; } return false; } public boolean isConnected(int x,int y) { return root(x)==root(y); } public int root(int x) { return parent[x] < 0 ? x : (parent[x] = root(parent[x])); } public int size(int x) { return -parent[root(x)]; } public ArrayList<ArrayList<Integer>> groups() { int n = parent.length; ArrayList<ArrayList<Integer>> g = new ArrayList<>(); HashMap<Integer,Integer> hm = new HashMap<>(); for(int i=0;i<n;i++) { int r = root(i); if (!hm.containsKey(r)) { hm.put(r, g.size()); g.add(new ArrayList<>()); } g.get(hm.get(r)).add(i); } return g; } public String toString() { return Arrays.toString(parent); } } String ns() throws IOException { while (!tok.hasMoreTokens()) { tok = new StringTokenizer(in.readLine(), " "); } return tok.nextToken(); } int ni() throws IOException { return Integer.parseInt(ns()); } long nl() throws IOException { return Long.parseLong(ns()); } double nd() throws IOException { return Double.parseDouble(ns()); } String[] nsa(int n) throws IOException { String[] res = new String[n]; for (int i = 0; i < n; i++) { res[i] = ns(); } return res; } int[] nia(int n) throws IOException { int[] res = new int[n]; for (int i = 0; i < n; i++) { res[i] = ni(); } return res; } long[] nla(int n) throws IOException { long[] res = new long[n]; for (int i = 0; i < n; i++) { res[i] = nl(); } return res; } public static void main(String[] args) throws IOException { in = new BufferedReader(new InputStreamReader(System.in)); out = new PrintWriter(System.out); tok = new StringTokenizer(""); Main main = new Main(); main.solve(); out.close(); } }
Submission Info
Submission Time | |
---|---|
Task | C - Interpretation |
User | CrazyBBB |
Language | Java8 (OpenJDK 1.8.0) |
Score | 400 |
Code Size | 3686 Byte |
Status | AC |
Exec Time | 294 ms |
Memory | 40120 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 | 94 ms | 8268 KB |
01-02.txt | AC | 106 ms | 8788 KB |
01-03.txt | AC | 112 ms | 9036 KB |
01-04.txt | AC | 117 ms | 8916 KB |
01-05.txt | AC | 119 ms | 8908 KB |
01-06.txt | AC | 118 ms | 8912 KB |
01-07.txt | AC | 107 ms | 8900 KB |
01-08.txt | AC | 119 ms | 8908 KB |
01-09.txt | AC | 109 ms | 8908 KB |
01-10.txt | AC | 113 ms | 9036 KB |
02-01.txt | AC | 294 ms | 40120 KB |
02-02.txt | AC | 267 ms | 29180 KB |
02-03.txt | AC | 251 ms | 27144 KB |
02-04.txt | AC | 273 ms | 33276 KB |
02-05.txt | AC | 266 ms | 29124 KB |
02-06.txt | AC | 273 ms | 33304 KB |
02-07.txt | AC | 268 ms | 29696 KB |
02-08.txt | AC | 238 ms | 28472 KB |
02-09.txt | AC | 288 ms | 31884 KB |
02-10.txt | AC | 258 ms | 33108 KB |
02-11.txt | AC | 250 ms | 31692 KB |
02-12.txt | AC | 265 ms | 32556 KB |
02-13.txt | AC | 258 ms | 31872 KB |
sample-01.txt | AC | 95 ms | 8272 KB |
sample-02.txt | AC | 95 ms | 8144 KB |