結果
問題 | No.1002 Twotone |
ユーザー | 0w1 |
提出日時 | 2021-01-02 16:49:07 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,763 ms / 5,000 ms |
コード長 | 4,462 bytes |
コンパイル時間 | 3,976 ms |
コンパイル使用メモリ | 244,488 KB |
実行使用メモリ | 126,148 KB |
最終ジャッジ日時 | 2023-08-02 10:58:34 |
合計ジャッジ時間 | 35,618 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 30 ms
36,000 KB |
testcase_02 | AC | 26 ms
31,704 KB |
testcase_03 | AC | 561 ms
85,516 KB |
testcase_04 | AC | 756 ms
90,524 KB |
testcase_05 | AC | 790 ms
120,700 KB |
testcase_06 | AC | 21 ms
25,476 KB |
testcase_07 | AC | 499 ms
46,112 KB |
testcase_08 | AC | 1,045 ms
95,364 KB |
testcase_09 | AC | 1,117 ms
89,208 KB |
testcase_10 | AC | 9 ms
10,420 KB |
testcase_11 | AC | 1,171 ms
89,984 KB |
testcase_12 | AC | 1,613 ms
74,112 KB |
testcase_13 | AC | 1,740 ms
101,916 KB |
testcase_14 | AC | 12 ms
13,268 KB |
testcase_15 | AC | 766 ms
54,388 KB |
testcase_16 | AC | 1,770 ms
82,176 KB |
testcase_17 | AC | 1,774 ms
77,044 KB |
testcase_18 | AC | 37 ms
42,836 KB |
testcase_19 | AC | 1,275 ms
103,912 KB |
testcase_20 | AC | 1,469 ms
88,408 KB |
testcase_21 | AC | 1,496 ms
87,712 KB |
testcase_22 | AC | 11 ms
12,684 KB |
testcase_23 | AC | 1,281 ms
65,940 KB |
testcase_24 | AC | 2,763 ms
107,744 KB |
testcase_25 | AC | 2,603 ms
107,680 KB |
testcase_26 | AC | 6 ms
8,116 KB |
testcase_27 | AC | 176 ms
96,968 KB |
testcase_28 | AC | 520 ms
95,152 KB |
testcase_29 | AC | 249 ms
108,068 KB |
testcase_30 | AC | 9 ms
9,916 KB |
testcase_31 | AC | 241 ms
107,308 KB |
testcase_32 | AC | 437 ms
93,212 KB |
testcase_33 | AC | 264 ms
118,480 KB |
testcase_34 | AC | 545 ms
126,148 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; /*^ vector extensions */ template<typename T> vector<T> concat(vector<T> a, vector<T> b) { a.insert(a.end(), b.begin(), b.end()); return a; } template<typename T, size_t sz> struct _Matrix_type { typedef vector<typename _Matrix_type<T, sz - 1>::type> type; }; template<typename T> struct _Matrix_type<T, 1> { typedef T type; }; template<typename T> struct _Matrix { static auto build(size_t s) { return vector<T>(s); } template<typename ...Args> static auto build(size_t f, Args... args) { return vector<typename _Matrix_type<T, 1 + sizeof...(args)>::type>(f, _Matrix<T>::build(args...)); } }; template<typename T, typename... Args> auto buildMatrix(Args... args) { return _Matrix<T>::build(args...); } /* vector extensions $*/ /*^ generic definitions */ template<typename F> struct _RecurFun : F { _RecurFun(F&& f) : F(forward<F>(f)) {} template<typename... Args> decltype(auto) operator()(Args&&... args) const { return F::operator()(*this, forward<Args>(args)...); } }; template<typename F> decltype(auto) RecurFun(F&& f) { return _RecurFun<F> { forward<F>(f) }; } /* generic definitions $*/ /*^ pbds */ #if __has_include(<ext/pb_ds/assoc_container.hpp>) #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; const int RandomIntSeed = chrono::high_resolution_clock::now().time_since_epoch().count(); struct HashInt { int operator()(int x) const { return x ^ RandomIntSeed; } }; template<typename T, typename U, typename H = hash<T>> using Gmap = gp_hash_table<T, U, H>; #endif /* pbds $*/ struct Centroid { vector<vector<int>> graph; vector<int> size, dead; Centroid(const vector<vector<int>> &g) : size(g.size()), dead(g.size()), graph(g) {} vector<int> findCentroids(int root) { vector<int> centroids; RecurFun([&](auto buildSize, int u, int p) -> void { size[u] = 1; for (int v : graph[u]) if (v != p && !dead[v]) buildSize(v, u), size[u] += size[v]; })(root, -1); RecurFun([&](auto buildCentroids, int u, int p) -> void { int ok = (size[root] - size[u]) * 2 <= size[root]; for (int v : graph[u]) if (v != p && !dead[v]) buildCentroids(v, u), ok &= size[v] * 2 <= size[root]; if (ok) centroids.push_back(u); })(root, -1); assert(1 <= centroids.size() && centroids.size() <= 2); return centroids; } }; int main() { ios::sync_with_stdio(false); int N, K; { cin >> N >> K; } vector<vector<int>> G(N); vector<Gmap<int, int>> C(N); { for (int u = 0; u + 1 < N; ++u) { int U, V, Z; { cin >> U >> V >> Z; --U, --V, --Z; } G[U].push_back(V); G[V].push_back(U); C[U][V] = Z; C[V][U] = Z; } } int64_t res = 0; { Centroid cd(G); queue<int> que({ cd.findCentroids(0)[0] }); int all = 0; // single color vector<int> cnt(K), cntx(K); vector<Gmap<int, int>> cnt2(K); while (que.size()) { int u = que.front(); que.pop(); for (int v : G[u]) if (!cd.dead[v]) { RecurFun([&](auto count, int u, int p, int a, int b) -> void { for (int v : G[u]) if (v != p && !cd.dead[v]) { if (a == C[u][v] || b == C[u][v]) count(v, u, a, b); else if (a == -1) count(v, u, C[u][v], b); } if (a == -1) res += (all - cnt[b]) + cntx[b]; else res += 1 + cnt[a] + cnt[b] + cnt2[a][b]; })(v, u, -1, C[u][v]); RecurFun([&](auto update, int u, int p, int a, int b) -> void { for (int v : G[u]) if (v != p && !cd.dead[v]) { if (a == C[u][v] || b == C[u][v]) update(v, u, a, b); else if (a == -1) update(v, u, C[u][v], b); } if (a == -1) ++cnt[b], ++all; else ++cntx[a], ++cntx[b], ++cnt2[a][b], ++cnt2[b][a]; })(v, u, -1, C[u][v]); } for (int v : G[u]) if (!cd.dead[v]) { RecurFun([&](auto update, int u, int p, int a, int b) -> void { for (int v : G[u]) if (v != p && !cd.dead[v]) { if (a == C[u][v] || b == C[u][v]) update(v, u, a, b); else if (a == -1) update(v, u, C[u][v], b); } if (a == -1) --cnt[b], --all; else --cntx[a], --cntx[b], --cnt2[a][b], --cnt2[b][a]; })(v, u, -1, C[u][v]); } cd.dead[u] = 1; for (int v : G[u]) if (!cd.dead[v]) que.push(cd.findCentroids(v)[0]); } } cout << res << endl; }