Submission #12138201


Source Code Expand

Copy
#include<bits/stdc++.h>

int main(){
    using namespace std;
    unsigned long N;
    cin >> N;
    vector<unsigned long> c(N);
    for(auto& i : c){
        cin >> i;
        --i;
    }
    vector edge(N, vector(0, 0UL));
    for(unsigned long i{1}, a, b; i < N; ++i){
        cin >> a >> b;
        edge[--a].push_back(--b);
        edge[b].push_back(a);
    }
    vector euler_tour(N, vector(0, 0UL));
    vector<unsigned long> sz(N);
    [dfs_impl = [&c, &edge, &euler_tour, &sz, &N](auto f, unsigned long now, unsigned long prev, unsigned long& t) -> unsigned long {
        sz[now] = 1;
        euler_tour[c[now]].push_back(1);
        for(const auto& i : edge[now])if(i != prev){
            sz[now] += f(f, i, now, t);
            euler_tour[c[now]].push_back(sz[now]);
        }
        euler_tour[c[now]].push_back(N + 1);
        return sz[now];
    }]{unsigned long t{0};dfs_impl(dfs_impl, 0, 0, t);}();
    for(unsigned long i{0}; i < N; ++i){
        unsigned long cnt{0};
        vector<unsigned long> tmp{0};
        for(const auto& now : euler_tour[i]){
            if(now == 1){
                tmp.push_back(1);
            }else if(now <= N){
                auto t = now - tmp.back();
                cnt += t * (t + 1) / 2;
                tmp.back() = now;
            }else{
                auto t = tmp.back();
                tmp.pop_back();
                tmp.back() += t;
            }
        }
        cnt += (N - tmp.back() + 1) * (N - tmp.back()) / 2;
        cout << N * (N + 1) / 2 - cnt << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task F - path pass i
User MMNMM
Language C++ (GCC 9.2.1)
Score 600
Code Size 1603 Byte
Status AC
Exec Time 587 ms
Memory 59068 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 5
AC × 24
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt
All line_01.txt, line_3_01.txt, random_01.txt, random_02.txt, random_03.txt, random_100_01.txt, random_100_02.txt, random_10_01.txt, random_10_02.txt, random_1_01.txt, random_1_02.txt, random_2_01.txt, random_2_02.txt, random_2_03.txt, random_3_01.txt, random_3_02.txt, random_3_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, star_01.txt, star_3_01.txt
Case Name Status Exec Time Memory
line_01.txt AC 525 ms 59068 KB
line_3_01.txt AC 422 ms 56192 KB
random_01.txt AC 587 ms 31248 KB
random_02.txt AC 572 ms 31028 KB
random_03.txt AC 578 ms 31156 KB
random_100_01.txt AC 495 ms 29508 KB
random_100_02.txt AC 496 ms 29508 KB
random_10_01.txt AC 492 ms 27920 KB
random_10_02.txt AC 502 ms 28128 KB
random_1_01.txt AC 493 ms 31428 KB
random_1_02.txt AC 497 ms 31512 KB
random_2_01.txt AC 497 ms 29352 KB
random_2_02.txt AC 488 ms 29356 KB
random_2_03.txt AC 498 ms 29428 KB
random_3_01.txt AC 487 ms 28048 KB
random_3_02.txt AC 500 ms 28160 KB
random_3_03.txt AC 468 ms 28072 KB
sample_01.txt AC 4 ms 3584 KB
sample_02.txt AC 2 ms 3496 KB
sample_03.txt AC 2 ms 3440 KB
sample_04.txt AC 2 ms 3432 KB
sample_05.txt AC 2 ms 3532 KB
star_01.txt AC 449 ms 30264 KB
star_3_01.txt AC 379 ms 31684 KB