Submission #1608220
Source Code Expand
import std.algorithm, std.conv, std.range, std.stdio, std.string; import std.container; // SList, DList, BinaryHeap void main() { auto rd1 = readln.split.to!(size_t[]), n = rd1[0], k = rd1[1], l = rd1[2]; auto readUf(size_t m) { auto uf = UnionFind(n); foreach (_1; 0..m) { auto rd2 = readln.splitter; auto u = rd2.front.to!size_t-1; rd2.popFront; auto v = rd2.front.to!size_t-1; uf.unite(u, v); } return uf; } auto uf1 = readUf(k), uf2 = readUf(l); struct P { size_t i, p1, p2; } auto p = new P[](n); foreach (i; 0..n) p[i] = P(i, uf1[i], uf2[i]); p.multiSort!("a.p1 < b.p1", "a.p2 < b.p2"); auto ans = new size_t[](n), prevP = p[0], prevI = size_t(0); foreach (i; 1..n) { if (p[i].p1 == prevP.p1 && p[i].p2 == prevP.p2) continue; foreach (j; prevI..i) ans[p[j].i] = i - prevI; prevP = p[i]; prevI = i; } foreach (j; prevI..n) ans[p[j].i] = n - prevI; foreach (i; 0..n) { write(ans[i]); if (i < n-1) write(" "); } writeln; } struct UnionFind { import std.algorithm, std.range; size_t[] p; // parent const size_t s; // sentinel const size_t n; size_t countForests; // number of forests size_t[] countNodes; // number of nodes in forests this(size_t n) { this.n = n; s = n; p = new size_t[](n); p[] = s; countForests = n; countNodes = new size_t[](n); countNodes[] = 1; } size_t opIndex(size_t i) { if (p[i] == s) { return i; } else { p[i] = this[p[i]]; return p[i]; } } bool unite(size_t i, size_t j) { auto pi = this[i], pj = this[j]; if (pi != pj) { p[pj] = pi; --countForests; countNodes[pi] += countNodes[pj]; return true; } else { return false; } } auto countNodesOf(size_t i) { return countNodes[this[i]]; } bool isSame(size_t i, size_t j) { return this[i] == this[j]; } auto groups() { auto g = new size_t[][](n); foreach (i; 0..n) g[this[i]] ~= i; return g.filter!(l => !l.empty); } }
Submission Info
Submission Time | |
---|---|
Task | D - Connectivity |
User | tesh |
Language | D (DMD64 v2.070.1) |
Score | 400 |
Code Size | 2170 Byte |
Status | AC |
Exec Time | 344 ms |
Memory | 17660 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_0.txt, subtask0_1.txt, subtask0_2.txt |
All | subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_0.txt | AC | 1 ms | 256 KB |
subtask0_1.txt | AC | 1 ms | 256 KB |
subtask0_2.txt | AC | 1 ms | 256 KB |
subtask1_0.txt | AC | 64 ms | 1404 KB |
subtask1_1.txt | AC | 129 ms | 15356 KB |
subtask1_10.txt | AC | 68 ms | 1532 KB |
subtask1_11.txt | AC | 118 ms | 12284 KB |
subtask1_12.txt | AC | 185 ms | 13180 KB |
subtask1_13.txt | AC | 344 ms | 17660 KB |
subtask1_14.txt | AC | 142 ms | 11260 KB |
subtask1_2.txt | AC | 121 ms | 11644 KB |
subtask1_3.txt | AC | 159 ms | 16764 KB |
subtask1_4.txt | AC | 145 ms | 11772 KB |
subtask1_5.txt | AC | 69 ms | 1532 KB |
subtask1_6.txt | AC | 112 ms | 12156 KB |
subtask1_7.txt | AC | 161 ms | 16252 KB |
subtask1_8.txt | AC | 249 ms | 16636 KB |
subtask1_9.txt | AC | 129 ms | 11260 KB |