結果
問題 | No.1002 Twotone |
ユーザー | 👑 hos.lyric |
提出日時 | 2020-02-28 22:05:32 |
言語 | D (dmd 2.105.2) |
結果 |
AC
|
実行時間 | 2,453 ms / 5,000 ms |
コード長 | 4,355 bytes |
コンパイル時間 | 1,083 ms |
コンパイル使用メモリ | 115,072 KB |
実行使用メモリ | 67,392 KB |
最終ジャッジ日時 | 2023-09-04 06:14:09 |
合計ジャッジ時間 | 34,642 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,384 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 574 ms
19,148 KB |
testcase_04 | AC | 776 ms
18,888 KB |
testcase_05 | AC | 754 ms
23,232 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 700 ms
14,960 KB |
testcase_08 | AC | 1,248 ms
33,084 KB |
testcase_09 | AC | 1,289 ms
20,196 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 1,442 ms
17,896 KB |
testcase_12 | AC | 1,807 ms
33,264 KB |
testcase_13 | AC | 1,922 ms
21,876 KB |
testcase_14 | AC | 2 ms
4,376 KB |
testcase_15 | AC | 1,017 ms
14,824 KB |
testcase_16 | AC | 2,064 ms
18,884 KB |
testcase_17 | AC | 2,041 ms
18,916 KB |
testcase_18 | AC | 2 ms
4,380 KB |
testcase_19 | AC | 1,105 ms
35,708 KB |
testcase_20 | AC | 1,350 ms
52,972 KB |
testcase_21 | AC | 1,344 ms
50,996 KB |
testcase_22 | AC | 2 ms
4,380 KB |
testcase_23 | AC | 1,428 ms
35,652 KB |
testcase_24 | AC | 2,453 ms
67,392 KB |
testcase_25 | AC | 2,392 ms
66,476 KB |
testcase_26 | AC | 2 ms
4,380 KB |
testcase_27 | AC | 205 ms
16,328 KB |
testcase_28 | AC | 332 ms
21,444 KB |
testcase_29 | AC | 318 ms
26,636 KB |
testcase_30 | AC | 2 ms
4,376 KB |
testcase_31 | AC | 308 ms
19,384 KB |
testcase_32 | AC | 336 ms
22,488 KB |
testcase_33 | AC | 318 ms
19,676 KB |
testcase_34 | AC | 2,208 ms
58,796 KB |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } int N, K; int[] A, B, C; int[][] G; long ans; void solveCentroidDecomp() { auto sz = new int[N]; auto del = new bool[N]; void dfsSz(int u, int p) { sz[u] = 1; foreach (i; G[u]) { const v = A[i] ^ B[i] ^ u; if (v != p) { dfsSz(v, u); sz[u] += sz[v]; } } } dfsSz(0, -1); // r: centroid void solveSubtree(int r) { debug { writefln("solveSubtree r = %s (del = %s)", r, del); } long[long] freq1Sum, freq2Sum; long[long] freq1, freq2; void dfs(int u, int p, int[] cs) { if (cs.length == 1) { ++freq1Sum[cs[0]]; ++freq1[cs[0]]; } else { const key = cs[0] + cs[1] * cast(long)(K); ++freq2Sum[key]; ++freq2[key]; } foreach (i; G[u]) { const v = A[i] ^ B[i] ^ u; if (!del[v] && v != p) { auto ccs = cs ~ C[i]; ccs = ccs.sort.uniq.array; if (ccs.length <= 2) { dfs(v, u, ccs); } } } } foreach (i; G[r]) { const v = A[i] ^ B[i] ^ r; if (!del[v]) { freq1.clear; freq2.clear; dfs(v, r, [C[i]]); const num1 = freq1.values.sum; foreach (c, val; freq1) { // 1-1 ans -= val * (num1 - val); } // 2-1, 2-2 foreach (key, val; freq2) { const c0 = key % K; const c1 = key / K; // 2-1 ans -= 2 * val * (((c0 in freq1) ? freq1[c0] : 0) + ((c1 in freq1) ? freq1[c1] : 0)); // 2-2 ans -= val * val; } } } const num1Sum = freq1Sum.values.sum; foreach (c, val; freq1Sum) { // 1-1 ans += val * (num1Sum - val); } // 2-1, 2-2 foreach (key, val; freq2Sum) { const c0 = key % K; const c1 = key / K; // 2-0 ans += 2 * val; // 2-1 ans += 2 * val * (((c0 in freq1Sum) ? freq1Sum[c0] : 0) + ((c1 in freq1Sum) ? freq1Sum[c1] : 0)); // 2-2 ans += val * val; } } void solveRec(int u) { for (; ; ) { int vm = -1; foreach (i; G[u]) { const v = A[i] ^ B[i] ^ u; if (!del[v]) { if (vm == -1 || sz[vm] < sz[v]) { vm = v; } } } if (vm == -1 || sz[u] >= 2 * sz[vm]) { solveSubtree(u); del[u] = true; foreach (i; G[u]) { const v = A[i] ^ B[i] ^ u; if (!del[v]) { solveRec(v); } } break; } else { sz[u] -= sz[vm]; sz[vm] += sz[u]; u = vm; } } } solveRec(0); } void main() { try { for (; ; ) { N = readInt(); K = readInt(); A = new int[N - 1]; B = new int[N - 1]; C = new int[N - 1]; foreach (i; 0 .. N - 1) { A[i] = readInt() - 1; B[i] = readInt() - 1; C[i] = readInt() - 1; } G = new int[][N]; foreach (i; 0 .. N - 1) { G[A[i]] ~= i; G[B[i]] ~= i; } ans = 0; solveCentroidDecomp(); ans /= 2; writeln(ans); } } catch (EOFException e) { } }