結果

問題 No.2892 Lime and Karin
ユーザー tottoripapertottoripaper
提出日時 2024-09-17 00:36:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,098 bytes
コンパイル時間 2,358 ms
コンパイル使用メモリ 212,456 KB
実行使用メモリ 30,628 KB
最終ジャッジ日時 2024-09-17 00:39:32
合計ジャッジ時間 175,574 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2,362 ms
6,940 KB
testcase_15 AC 2,695 ms
6,944 KB
testcase_16 AC 5,099 ms
8,704 KB
testcase_17 AC 560 ms
6,944 KB
testcase_18 AC 4,447 ms
8,832 KB
testcase_19 AC 7,293 ms
10,496 KB
testcase_20 AC 85 ms
6,940 KB
testcase_21 AC 2,358 ms
7,296 KB
testcase_22 AC 3,669 ms
8,576 KB
testcase_23 AC 985 ms
6,940 KB
testcase_24 AC 7,421 ms
10,624 KB
testcase_25 AC 7,153 ms
10,624 KB
testcase_26 AC 7,229 ms
10,496 KB
testcase_27 AC 7,282 ms
10,624 KB
testcase_28 AC 7,364 ms
10,624 KB
testcase_29 AC 7,178 ms
10,752 KB
testcase_30 AC 7,326 ms
10,624 KB
testcase_31 AC 7,569 ms
10,624 KB
testcase_32 AC 7,255 ms
10,624 KB
testcase_33 AC 7,474 ms
10,752 KB
testcase_34 AC 5,306 ms
10,896 KB
testcase_35 AC 5,171 ms
10,892 KB
testcase_36 AC 6,296 ms
10,896 KB
testcase_37 AC 6,192 ms
10,892 KB
testcase_38 AC 6,265 ms
10,764 KB
testcase_39 AC 5,986 ms
19,920 KB
testcase_40 AC 7,483 ms
27,904 KB
testcase_41 TLE -
testcase_42 AC 6,330 ms
28,928 KB
testcase_43 TLE -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using ll = std::int64_t;

void dfs(
    int v,
    int p,
    int &counter,
    std::vector<int> &in,
    std::vector<int> &out,
    std::vector<int> &diff,
    const std::vector<std::vector<int>> &G,
    const std::string &S
){
    in[v] = counter;
    counter += 1;
    diff[in[v]] = S[v - 1] == '1' ? 1 : -1;
    if(p != -1){
        diff[in[v]] += diff[in[p]];
    }

    for(auto &w : G[v]){
        if(w != p){
            dfs(w, v, counter, in, out, diff, G, S);
        }
    }

    out[v] = counter;
}

ll search(
    int x, int l, int r,
    const std::vector<int> &diff,
    const std::vector<int> &diff_group,
    const std::vector<int> &incr,
    const int B
){
    ll res = 0;
    while(l < r && l % B > 0){
        if(diff[l] + incr[l / B] >= x){
            res += 1;
        }
        l += 1;
    }
    while(l < r && r % B > 0){
        if(diff[r - 1] + incr[(r - 1) / B] >= x){
            res += 1;
        }
        r -= 1;
    }
    while(l < r){
        int last = std::min<int>(l + B, diff_group.size());
        res +=
            diff_group.begin() + last
            - std::lower_bound(diff_group.begin() + l, diff_group.begin() + last, x - incr[l / B]);
        l = last;
    }

    return res;
}

void add(
    int x, int l, int r,
    std::vector<int> &diff,
    std::vector<int> &diff_group,
    std::vector<int> &incr,
    const int B
){
    auto update_point = [&](int i){
        int first = i / B * B, last = std::min<int>(first + B, diff_group.size());
        if(x == -1){
            int j =
                std::lower_bound(diff_group.begin() + first, diff_group.begin() + last, diff[i])
                - diff_group.begin();
            diff_group[j] += x;
        }else{
            int j =
                std::upper_bound(diff_group.begin() + first, diff_group.begin() + last, diff[i])
                - diff_group.begin();
            j -= 1;
            diff_group[j] += x;
        }
        diff[i] += x;
    };

    while(l < r && l % B > 0){
        update_point(l);
        l += 1;
    }
    while(l < r && r % B > 0){
        update_point(r - 1);
        r -= 1;
    }
    l /= B;
    r /= B;
    while(l < r){
        incr[l] += x;
        l += 1;
    }
}

ll dfs2(
    int v,
    int p,
    const std::vector<int> &in,
    const std::vector<int> &out,
    std::vector<int> &diff,
    std::vector<int> &diff_group,
    std::vector<int> &incr,
    const std::vector<std::vector<int>> &G,
    const std::string &S,
    const int B
){
    ll res = 0;
    res += search(1, 0, diff.size(), diff, diff_group, incr, B);

    int xv = S[v - 1] == '1' ? 1 : -1;
    for(auto &w : G[v]){
        if(w != p){
            int xw = S[w - 1] == '1' ? 1 : -1;
            add(xw, 0, in[w], diff, diff_group, incr, B);
            add(-xv, in[w], out[w], diff, diff_group, incr, B);
            add(xw, out[w], diff.size(), diff, diff_group, incr, B);
            res += dfs2(w, v, in, out, diff, diff_group, incr, G, S, B);
            add(-xw, 0, in[w], diff, diff_group, incr, B);
            add(xv, in[w], out[w], diff, diff_group, incr, B);
            add(-xw, out[w], diff.size(), diff, diff_group, incr, B);
        }
    }

    return res;
}

int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int N;
    std::cin >> N;

    std::vector<std::vector<int>> G(N + 1);
    for(int i=0;i<N-1;i++){
        int u, v;
        std::cin >> u >> v;

        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    std::string S;
    std::cin >> S;

    std::vector<int> in(N + 1), out(N + 1), diff(N, 0);
    {
        int counter = 0;
        dfs(1, -1, counter, in, out, diff, G, S);
    }

    const int B = std::sqrt(N);
    std::vector<int> diff_group(diff), incr((N + B - 1) / B, 0);
    for(int i=0;i<N;i+=B){
        std::sort(diff_group.begin() + i, diff_group.begin() + std::min(i + B, N));
    }

    ll res = dfs2(1, -1, in, out, diff, diff_group, incr, G, S, B);
    int n = std::count(S.begin(), S.end(), '1');
    res -= n;
    res = res / 2 + n;
    std::cout << res << std::endl;
}
0