Submission #1795640
Source Code Expand
import std.algorithm, std.conv, std.range, std.stdio, std.string; void main() { auto rd = readln.split.to!(int[]), n = rd[0], q = rd[1]; auto uf = UnionFind!int(n), eo = new bool[](n); foreach (_; 0..q) { auto rd2 = readln.splitter; auto w = rd2.front.to!int; rd2.popFront(); auto x = rd2.front.to!int-1; rd2.popFront(); auto y = rd2.front.to!int-1; rd2.popFront(); auto z = rd2.front.to!int%2 == 0; auto px = uf[x], py = uf[y]; if (w == 1) { if (px == py) { if (z && eo[x] != eo[y] || !z && eo[x] == eo[y]) uf.superForest[px] = true; } else { if (z && eo[x] != eo[y] || !z && eo[x] == eo[y]) { foreach (i; uf.countNodes[px] > uf.countNodes[py] ? uf.nodes[py] : uf.nodes[px]) eo[i] = !eo[i]; } uf.unite(x, y); } } else { writeln(px == py && (eo[x] == eo[y] || uf.superForest[px]) ? "YES" : "NO"); } } } struct UnionFind(T) { import std.algorithm, std.range; T[] p; // parent const T s; // sentinel const T n; T countForests; // number of forests T[] countNodes; // number of nodes in forests T[][] nodes; bool[] superForest; this(T n) { this.n = n; s = n; p = new T[](n); p[] = s; countForests = n; countNodes = new T[](n); countNodes[] = 1; nodes = new T[][](n); foreach (i; 0..n) nodes[i] = [i]; superForest = new bool[](n); } T opIndex(T i) { if (p[i] == s) { return i; } else { p[i] = this[p[i]]; return p[i]; } } bool unite(T i, T j) { auto pi = this[i], pj = this[j]; if (pi != pj) { p[pj] = pi; --countForests; if (countNodes[pi] > countNodes[pj]) { nodes[pi] ~= nodes[pj]; } else { nodes[pj] ~= nodes[pi]; nodes[pi] = nodes[pj]; } nodes[pj] = []; superForest[pi] |= superForest[pj]; countNodes[pi] += countNodes[pj]; return true; } else { return false; } } auto countNodesOf(T i) { return countNodes[this[i]]; } bool isSame(T i, T j) { return this[i] == this[j]; } auto groups() { auto g = new T[][](n); foreach (i; 0..n) g[this[i]] ~= i; return g.filter!(l => !l.empty); } }
Submission Info
Submission Time | |
---|---|
Task | D - 偶数メートル |
User | tesh |
Language | D (DMD64 v2.070.1) |
Score | 100 |
Code Size | 2361 Byte |
Status | AC |
Exec Time | 103 ms |
Memory | 13564 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 70 / 70 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 | sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt |
Subtask2 | sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
subtask1_01.txt | AC | 2 ms | 380 KB |
subtask1_02.txt | AC | 2 ms | 256 KB |
subtask1_03.txt | AC | 3 ms | 380 KB |
subtask1_04.txt | AC | 2 ms | 256 KB |
subtask1_05.txt | AC | 2 ms | 380 KB |
subtask1_06.txt | AC | 2 ms | 380 KB |
subtask1_07.txt | AC | 2 ms | 256 KB |
subtask1_08.txt | AC | 3 ms | 380 KB |
subtask1_09.txt | AC | 3 ms | 508 KB |
subtask1_10.txt | AC | 3 ms | 508 KB |
subtask1_11.txt | AC | 3 ms | 508 KB |
subtask1_12.txt | AC | 3 ms | 508 KB |
subtask1_13.txt | AC | 3 ms | 508 KB |
subtask1_14.txt | AC | 3 ms | 508 KB |
subtask1_15.txt | AC | 3 ms | 508 KB |
subtask1_16.txt | AC | 3 ms | 508 KB |
subtask1_17.txt | AC | 3 ms | 508 KB |
subtask1_18.txt | AC | 3 ms | 508 KB |
subtask1_19.txt | AC | 3 ms | 508 KB |
subtask1_20.txt | AC | 3 ms | 508 KB |
subtask1_21.txt | AC | 3 ms | 508 KB |
subtask1_22.txt | AC | 3 ms | 508 KB |
subtask1_23.txt | AC | 4 ms | 2556 KB |
subtask1_24.txt | AC | 3 ms | 508 KB |
subtask1_25.txt | AC | 3 ms | 508 KB |
subtask1_26.txt | AC | 3 ms | 508 KB |
subtask1_27.txt | AC | 3 ms | 508 KB |
subtask1_28.txt | AC | 3 ms | 508 KB |
subtask1_29.txt | AC | 3 ms | 508 KB |
subtask2_01.txt | AC | 29 ms | 1916 KB |
subtask2_02.txt | AC | 74 ms | 7932 KB |
subtask2_03.txt | AC | 8 ms | 1788 KB |
subtask2_04.txt | AC | 69 ms | 6268 KB |
subtask2_05.txt | AC | 39 ms | 7932 KB |
subtask2_06.txt | AC | 38 ms | 5756 KB |
subtask2_07.txt | AC | 69 ms | 7548 KB |
subtask2_08.txt | AC | 75 ms | 8956 KB |
subtask2_09.txt | AC | 47 ms | 5500 KB |
subtask2_10.txt | AC | 89 ms | 9468 KB |
subtask2_11.txt | AC | 86 ms | 9852 KB |
subtask2_12.txt | AC | 89 ms | 9724 KB |
subtask2_13.txt | AC | 90 ms | 9212 KB |
subtask2_14.txt | AC | 91 ms | 10236 KB |
subtask2_15.txt | AC | 87 ms | 9596 KB |
subtask2_16.txt | AC | 87 ms | 10364 KB |
subtask2_17.txt | AC | 88 ms | 10364 KB |
subtask2_18.txt | AC | 99 ms | 10236 KB |
subtask2_19.txt | AC | 87 ms | 9596 KB |
subtask2_20.txt | AC | 86 ms | 9340 KB |
subtask2_21.txt | AC | 99 ms | 11132 KB |
subtask2_22.txt | AC | 101 ms | 12412 KB |
subtask2_23.txt | AC | 100 ms | 10748 KB |
subtask2_24.txt | AC | 100 ms | 11004 KB |
subtask2_25.txt | AC | 102 ms | 10748 KB |
subtask2_26.txt | AC | 103 ms | 10876 KB |
subtask2_27.txt | AC | 101 ms | 11004 KB |
subtask2_28.txt | AC | 100 ms | 10748 KB |
subtask2_29.txt | AC | 101 ms | 13564 KB |
subtask2_30.txt | AC | 76 ms | 10236 KB |