結果
問題 | No.1769 Don't Stop the Game |
ユーザー | first_vil |
提出日時 | 2021-10-22 21:10:48 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 536 ms / 3,000 ms |
コード長 | 3,972 bytes |
コンパイル時間 | 2,823 ms |
コンパイル使用メモリ | 221,176 KB |
実行使用メモリ | 69,544 KB |
最終ジャッジ日時 | 2023-09-12 04:46:58 |
合計ジャッジ時間 | 13,564 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 3 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 3 ms
4,380 KB |
testcase_06 | AC | 3 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 329 ms
18,228 KB |
testcase_09 | AC | 238 ms
15,452 KB |
testcase_10 | AC | 368 ms
26,136 KB |
testcase_11 | AC | 225 ms
13,988 KB |
testcase_12 | AC | 418 ms
21,472 KB |
testcase_13 | AC | 422 ms
21,456 KB |
testcase_14 | AC | 423 ms
22,024 KB |
testcase_15 | AC | 421 ms
21,816 KB |
testcase_16 | AC | 426 ms
21,944 KB |
testcase_17 | AC | 453 ms
24,956 KB |
testcase_18 | AC | 536 ms
35,728 KB |
testcase_19 | AC | 501 ms
41,480 KB |
testcase_20 | AC | 509 ms
42,344 KB |
testcase_21 | AC | 509 ms
42,748 KB |
testcase_22 | AC | 515 ms
42,492 KB |
testcase_23 | AC | 425 ms
21,404 KB |
testcase_24 | AC | 423 ms
21,676 KB |
testcase_25 | AC | 193 ms
21,940 KB |
testcase_26 | AC | 347 ms
42,772 KB |
testcase_27 | AC | 270 ms
48,620 KB |
testcase_28 | AC | 390 ms
69,544 KB |
testcase_29 | AC | 383 ms
56,800 KB |
testcase_30 | AC | 386 ms
56,872 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for(int i=0;i<n;++i) template<class T> inline void print(const T & a) { cout << a << "\n"; } template<class T, class... Ts> inline void print(const T & a, const Ts&... ts) { cout << a << " "; print(ts...); } template<class T> inline void print(const vector<T>&v) { for (int i = 0; i < v.size(); ++i)cout << v[i] << (i == v.size() - 1 ? "\n" : " "); } pair<int, int> operator+(const pair<int, int>& a, const pair<int, int>& b) { return { a.first + b.first,a.second + b.second }; } pair<int, int> operator-(const pair<int, int>& a, const pair<int, int>& b) { return { a.first - b.first,a.second - b.second }; } pair<int, int> operator+=(pair<int, int>& a, const pair<int, int>& b) { a.first += b.first; a.second += b.second; return a; } template<class T> class BinaryIndexedTree { int n; vector<T> dat; public: BinaryIndexedTree(int n) : n(n), dat(n + 1) {}; void add(int i, T a) { for (++i; i <= n; i += i & -i)dat[i] += a; } T sum(int r) {// sum of [0,r) T res = {}; for (; r; r -= r & -r)res += dat[r]; return res; } T sum(int l, int r) {// sum of [l,r) if (l < 0 || n < r || l > r)return {}; return sum(r) - sum(l); } }; int main() { int n; cin >> n; vector<vector<pair<int, int>>> g(n); rep(i, n - 1) { int a, b, c; cin >> a >> b >> c; --a, --b; g[a].emplace_back(b, c); g[b].emplace_back(a, c); } int now = 0; vector<int> siz(n, 1), x(n), in(n), out(n); auto dfs0 = [&](auto&& f, int cur, int par)->void { in[cur] = now; ++now; for (auto [to, weight] : g[cur]) { if (to == par)continue; x[to] = x[cur] ^ weight; f(f, to, cur); siz[cur] += siz[to]; } out[cur] = now; }; dfs0(dfs0, 0, -1); auto sorted_x = x; sort(sorted_x.begin(), sorted_x.end()); sorted_x.erase(unique(sorted_x.begin(), sorted_x.end()), sorted_x.end()); rep(i, n)x[i] = lower_bound(sorted_x.begin(), sorted_x.end(), x[i]) - sorted_x.begin();//compress vector<vector<int>> idxs(sorted_x.size()); auto dfs1 = [&](auto&& f, int cur, int par)->void { idxs[x[cur]].push_back(in[cur]); for (auto [to, weight] : g[cur]) { if (to == par)continue; f(f, to, cur); } }; dfs1(dfs1, 0, -1); vector<BinaryIndexedTree<pair<int, int>>> y_cnt; y_cnt.reserve(idxs.size()); rep(i, idxs.size()) { sort(idxs[i].begin(), idxs[i].end()); y_cnt.emplace_back(idxs[i].size()); } ll ans = ll(n) * (n - 1); auto dfs2 = [&](auto&& f, int cur, int par)->void { int l = lower_bound(idxs[x[cur]].begin(), idxs[x[cur]].end(), in[cur]) - idxs[x[cur]].begin(); int r = lower_bound(idxs[x[cur]].begin(), idxs[x[cur]].end(), out[cur]) - idxs[x[cur]].begin(); for (auto [to, weight] : g[cur]) { if (to == par)continue; f(f, to, cur); } { auto [y, cnt] = y_cnt[x[cur]].sum(l, r); ans -= y;//case-1 y_cnt[x[cur]].add(l, pair<int, int>(siz[cur] - y, 1 - cnt)); } if (cur == 0) { rep(i, idxs.size())if (i != x[cur]) { auto [y, cnt] = y_cnt[i].sum(0, idxs[i].size()); ans -= ll(y) * cnt;//case-3 } } else { l = lower_bound(idxs[x[par]].begin(), idxs[x[par]].end(), in[cur]) - idxs[x[par]].begin(); r = lower_bound(idxs[x[par]].begin(), idxs[x[par]].end(), out[cur]) - idxs[x[par]].begin(); auto [y, cnt] = y_cnt[x[par]].sum(l, r); ans -= ll(cnt) * (n - siz[cur]);//case-2 ans -= ll(y) * cnt;//case-3 ans += siz[cur];//case-3 } }; dfs2(dfs2, 0, -1); cout << ans << "\n"; return 0; }