Submission #6326265
Source Code Expand
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric; struct UFTree(T) { struct Node { T parent; T rank = 1; } /// this(T n) { nodes.length = n; sizes.length = n; foreach (i, ref node; nodes) { node = Node(i.to!T); sizes[i] = 1; } } /// bool unite(T a, T b) { a = root(a); b = root(b); if (a == b) return false; if (nodes[a].rank < nodes[b].rank) { sizes[nodes[a].parent] += sizes[nodes[b].parent]; nodes[b].parent = nodes[a].parent; } else { sizes[nodes[b].parent] += sizes[nodes[a].parent]; nodes[a].parent = nodes[b].parent; if (nodes[a].rank == nodes[b].rank) nodes[a].rank += 1; } return true; } /// bool is_same(T a, T b) { return root(a) == root(b); } /// T size(T i) { return sizes[root(i)]; } private: Node[] nodes; T[] sizes; T root(T i) { if (nodes[i].parent == i) return i; return nodes[i].parent = root(nodes[i].parent); } } /// UFTree!T uftree(T)(T n) { return UFTree!T(n); } void main() { auto nm = readln.split.to!(int[]); auto N = nm[0]; auto M = nm[1]; auto uft = uftree(N+M); foreach (int n; 0..N) { foreach (l; readln.split.to!(int[])[1..$]) { uft.unite(n, N+l-1); } } foreach (int i; 0..N-1) { if (!uft.is_same(i, i+1)) { writeln("NO"); return; } } writeln("YES"); }
Submission Info
Submission Time | |
---|---|
Task | C - Interpretation |
User | cedretaber |
Language | D (DMD64 v2.070.1) |
Score | 400 |
Code Size | 1768 Byte |
Status | AC |
Exec Time | 100 ms |
Memory | 7428 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 | 1 ms | 256 KB |
01-02.txt | AC | 1 ms | 380 KB |
01-03.txt | AC | 2 ms | 508 KB |
01-04.txt | AC | 2 ms | 508 KB |
01-05.txt | AC | 2 ms | 380 KB |
01-06.txt | AC | 2 ms | 380 KB |
01-07.txt | AC | 2 ms | 380 KB |
01-08.txt | AC | 2 ms | 380 KB |
01-09.txt | AC | 2 ms | 380 KB |
01-10.txt | AC | 2 ms | 508 KB |
02-01.txt | AC | 33 ms | 2556 KB |
02-02.txt | AC | 94 ms | 2428 KB |
02-03.txt | AC | 38 ms | 3580 KB |
02-04.txt | AC | 73 ms | 3324 KB |
02-05.txt | AC | 86 ms | 3324 KB |
02-06.txt | AC | 71 ms | 3452 KB |
02-07.txt | AC | 93 ms | 4092 KB |
02-08.txt | AC | 92 ms | 3964 KB |
02-09.txt | AC | 100 ms | 3580 KB |
02-10.txt | AC | 61 ms | 7428 KB |
02-11.txt | AC | 61 ms | 7136 KB |
02-12.txt | AC | 61 ms | 2940 KB |
02-13.txt | AC | 60 ms | 4860 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |