結果

問題 No.1769 Don't Stop the Game
ユーザー first_vilfirst_vil
提出日時 2021-10-22 23:15:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 528 ms / 3,000 ms
コード長 3,179 bytes
コンパイル時間 2,616 ms
コンパイル使用メモリ 219,660 KB
実行使用メモリ 55,772 KB
最終ジャッジ日時 2023-09-12 04:46:20
合計ジャッジ時間 14,146 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 335 ms
17,272 KB
testcase_09 AC 229 ms
13,392 KB
testcase_10 AC 349 ms
17,248 KB
testcase_11 AC 226 ms
13,324 KB
testcase_12 AC 402 ms
20,408 KB
testcase_13 AC 411 ms
20,580 KB
testcase_14 AC 424 ms
20,764 KB
testcase_15 AC 421 ms
20,700 KB
testcase_16 AC 432 ms
20,596 KB
testcase_17 AC 480 ms
20,876 KB
testcase_18 AC 515 ms
21,592 KB
testcase_19 AC 520 ms
22,244 KB
testcase_20 AC 526 ms
22,192 KB
testcase_21 AC 515 ms
22,236 KB
testcase_22 AC 528 ms
22,240 KB
testcase_23 AC 413 ms
20,652 KB
testcase_24 AC 420 ms
20,612 KB
testcase_25 AC 157 ms
20,984 KB
testcase_26 AC 241 ms
22,516 KB
testcase_27 AC 218 ms
53,924 KB
testcase_28 AC 291 ms
55,772 KB
testcase_29 AC 291 ms
39,772 KB
testcase_30 AC 291 ms
39,800 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<n;++i)

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;
        int par_idx = -1;
        rep(i, g[cur].size()) {
            auto [to, weight] = g[cur][i];
            if (to == par) {
                par_idx = i;
                continue;
            }
            x[to] = x[cur] ^ weight;
            f(f, to, cur);
            siz[cur] += siz[to];
        }
        if (par_idx != -1) {
            swap(g[cur][par_idx], g[cur].back());
            g[cur].pop_back();
        }
        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

    auto dfs1 = [&](auto&& f, int cur)->void {
        sort(g[cur].begin(), g[cur].end(), [&](const pair<int,int>& i, const pair<int,int>& j) {return siz[i.first] > siz[j.first]; });
        for (auto [to, weight] : g[cur]) {
            f(f, to);
        }
    };
    dfs1(dfs1, 0);
    vector<int> y_sum(sorted_x.size()), cnt_sum(sorted_x.size());

    vector<int> y(n, -1), cnt(n, -1);
    ll ans = ll(n) * (n - 1);
    int parity[2] = { 1,-1 };
    auto dfs3 = [&](auto&& f, int cur, bool type)->void {
        y_sum[x[cur]] += parity[type] * y[cur];
        cnt_sum[x[cur]] += parity[type] * cnt[cur];
        for (int i = 0; i < g[cur].size(); ++i) {
            f(f, g[cur][i].first, type);
        }
    };
    auto dfs2 = [&](auto&& f, int cur, int par, bool type)->void {
        for (int i = 1; i < g[cur].size(); ++i) {
            f(f, g[cur][i].first, cur, true);
        }
        if (!g[cur].empty())f(f, g[cur][0].first, cur, false);
        for (int i = 1; i < g[cur].size(); ++i) {
            dfs3(dfs3, g[cur][i].first, false);
        }

        if (y[cur] == -1) {
            y[cur] = siz[cur] - y_sum[x[cur]];
            cnt[cur] = 1 - cnt_sum[x[cur]];
        }
        ans -= y_sum[x[cur]];//case-1
        y_sum[x[cur]] += y[cur];
        cnt_sum[x[cur]] += cnt[cur];

        if (cur == 0) {
            rep(i, sorted_x.size())if (i != x[cur]) {
                ans -= ll(y_sum[i]) * cnt_sum[i];//case-3
            }
        }
        else {
            ans -= ll(cnt_sum[x[par]]) * (n - siz[cur]);//case-2
            ans -= ll(y_sum[x[par]]) * cnt_sum[x[par]];//case-3

            ans += siz[cur];//case-3
        }

        if (type) {
            for (int i = 0; i < g[cur].size(); ++i) {
                dfs3(dfs3, g[cur][i].first, true);
            }
            y_sum[x[cur]] -= y[cur];
            cnt_sum[x[cur]] -= cnt[cur];
        }
    };
    dfs2(dfs2, 0, -1, false);
    cout << ans << "\n";

    return 0;
}
0