Submission #992510
Source Code Expand
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; final class UnionFind { int[] data; public UnionFind(int n) { data = new int[n]; for (int i = 0; i < n; i++) { data[i] = -1; } } boolean union(int x, int y) { x = root(x); y = root(y); if (x == y) return false; if (data[y] < data[x]) { x ^= y; y ^= x; x ^= y; } data[x] += data[y]; data[y] = x; return true; } boolean findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : (data[x] = root(data[x])); } int size(int x) { return -data[root(x)]; } } public class Main { private static void solve() { int n = nei(); int m = nei(); UnionFind uf = new UnionFind(m + n); for (int i = 0; i < n; i++) { int ki = nei(); for (int j = 0; j < ki; j++) { int li = nei()-1; uf.union(m + i, li); } } for (int i = 0; i < n; i++) { if (!uf.findSet(m, m + i)) { out("NO"); return; } } out("YES"); } static int abs(int x) { return x < 0 ? -x : x; } static long abs(long x) { return x < 0 ? -x : x; } static int min(int a, int b) { return a < b ? a : b; } static long min(long a, long b) { return a < b ? a : b; } static int max(int a, int b) { return a > b ? a : b; } static long max(long a, long b) { return a > b ? a : b; } static int clamp(int a, int min, int max) { return a < min ? min : a > max ? max : a; } static long clamp(long a, long min, long max) { return a < min ? min : a > max ? max : a; } static void out(String val) { IO.out(val); } static void out(Object val) { IO.out(String.valueOf(val)); } static void out(int val) { IO.out(String.valueOf(val)); } static void out(long val) { IO.out(String.valueOf(val)); } static void out(char val) { IO.out(String.valueOf(val)); } static void out(float val) { IO.out(String.valueOf(val)); } static void out(double val) { IO.out(String.valueOf(val)); } static void out(boolean val) { IO.out(String.valueOf(val)); } static String nes() { return IO.next(); } static int nei() { return IO.nextInt(); } static long nel() { return IO.nextLong(); } static int parseInt(String val) { return Integer.parseInt(val); } static int parseInt(char val) { return Integer.parseInt(String.valueOf(val)); } static long parseLong(String val) { return Long.parseLong(val); } public static void main(String[] args) { solve(); IO.flush(); } } final class IO { private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out, false); private static final byte[] buffer = new byte[1024]; private static int ptr = 0; private static int len = 0; private static boolean hasNextByte() { if (ptr < len) return true; ptr = 0; try { len = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } return len > 0; } private static int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } static boolean hasNext() { byte c; while (hasNextByte() && ((c = buffer[ptr]) < '!' || c > '~')) ptr++; return hasNextByte(); } static String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (b >= '!' && b <= '~') { sb.append((char) b); b = readByte(); } return sb.toString(); } static long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; int sign = 1; int b = readByte(); if (b == '-') { sign = -1; b = readByte(); } if (b < '0' || '9' < b) throw new NumberFormatException(); while (true) { if ('0' <= b && b <= '9') n = n * 10 + b - '0'; else if (b == -1 || b < '!' || b > '~') return n * sign; else throw new NumberFormatException(); b = readByte(); } } static int nextInt() { if (!hasNext()) throw new NoSuchElementException(); int n = 0; int sign = 1; int b = readByte(); if (b == '-') { sign = -1; b = readByte(); } if (b < '0' || '9' < b) throw new NumberFormatException(); while (true) { if ('0' <= b && b <= '9') n = n * 10 + b - '0'; else if (b == -1 || b < '!' || b > '~') return n * sign; else throw new NumberFormatException(); b = readByte(); } } static void out(String val) { out.println(val); } static void flush() { out.flush(); } }
Submission Info
Submission Time | |
---|---|
Task | C - Interpretation |
User | saharan |
Language | Java8 (OpenJDK 1.8.0) |
Score | 400 |
Code Size | 4778 Byte |
Status | AC |
Exec Time | 154 ms |
Memory | 10756 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 | 97 ms | 8400 KB |
01-02.txt | AC | 98 ms | 8400 KB |
01-03.txt | AC | 98 ms | 8276 KB |
01-04.txt | AC | 99 ms | 8404 KB |
01-05.txt | AC | 98 ms | 8532 KB |
01-06.txt | AC | 111 ms | 8532 KB |
01-07.txt | AC | 99 ms | 8400 KB |
01-08.txt | AC | 108 ms | 8276 KB |
01-09.txt | AC | 99 ms | 8276 KB |
01-10.txt | AC | 101 ms | 8528 KB |
02-01.txt | AC | 129 ms | 9808 KB |
02-02.txt | AC | 123 ms | 9812 KB |
02-03.txt | AC | 131 ms | 9296 KB |
02-04.txt | AC | 146 ms | 10068 KB |
02-05.txt | AC | 139 ms | 10232 KB |
02-06.txt | AC | 153 ms | 10068 KB |
02-07.txt | AC | 137 ms | 10228 KB |
02-08.txt | AC | 131 ms | 9552 KB |
02-09.txt | AC | 154 ms | 10756 KB |
02-10.txt | AC | 138 ms | 9964 KB |
02-11.txt | AC | 137 ms | 9936 KB |
02-12.txt | AC | 128 ms | 9552 KB |
02-13.txt | AC | 135 ms | 10064 KB |
sample-01.txt | AC | 96 ms | 8400 KB |
sample-02.txt | AC | 96 ms | 8272 KB |