Submission #240856

#	Time	Username	Problem	Language	Result	Execution time	Memory
240856		mhy908	Unique Cities (JOI19_ho_t5)	C++14	100 / 100	567 ms	36728 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
int n, m;
vector<int> link[200010];
int col[200010], d[200010], h[200010], ans[200010];
void dfs1(int num, int par){
    d[num]=d[par]+1, h[num]=1;
    for(auto i:link[num]){
        if(i==par)continue;
        dfs1(i, num);
        h[num]=max(h[num], h[i]+1);
    }
}
int stk[200010], re, cnt[200010], anss;
inline void update(int col, int num){
    if(!cnt[col])anss++;
    cnt[col]+=num;
    if(!cnt[col])anss--;
}
void dfs2(int num, int par){
    int max1=0, max2=0, maxnum=0;
    for(auto i:link[num]){
        if(i==par)continue;
        if(max2<=h[i]){
            if(max1<=h[i]){
                max2=max1;
                max1=h[i];
                maxnum=i;
            }
            else max2=h[i];
        }
    }
    while(re&&d[num]-d[stk[re]]<=max2)update(col[stk[re--]], -1);
    if(maxnum){
        update(col[num], 1);
        stk[++re]=num;
        dfs2(maxnum, num);
    }
    while(re&&d[num]-d[stk[re]]<=max1)update(col[stk[re--]], -1);
    ans[num]=max(ans[num], anss);
    for(auto i:link[num]){
        if(i==par||i==maxnum)continue;
        if(stk[re]!=num){
            update(col[num], 1);
            stk[++re]=num;
        }
        dfs2(i, num);
    }
    if(stk[re]==num){
        update(col[num], -1);
        re--;
    }
}
int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<n; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        link[a].eb(b);
        link[b].eb(a);
    }
    for(int i=1; i<=n; i++)scanf("%d", &col[i]);
    dfs1(1, 0);
    int rt1=max_element(d+1, d+n+1)-d;
    dfs1(rt1, 0);
    dfs2(rt1, 0);
    int rt2=max_element(d+1, d+n+1)-d;
    dfs1(rt2, 0);
    dfs2(rt2, 0);
    for(int i=1; i<=n; i++)printf("%d\n", ans[i]);
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:63:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=n; i++)scanf("%d", &col[i]);
                            ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32