Submission #240331

#	Time	Username	Problem	Language	Result	Execution time	Memory
240331		mhy908	Capital City (JOI20_capital_city)	C++14	100 / 100	950 ms	46572 KiB

capital_city

#include <bits/stdc++.h>
#define eb emplace_back
const int inf=987654321;
using namespace std;
typedef long long LL;
int n, k, col[200010], siz[200010];
vector<int> link[200010], vcm[200010];
void dfs(int num, int par){
    siz[num]=1;
    vcm[col[num]].eb(num);
    for(auto i:link[num]){
        if(i==par)continue;
        dfs(i, num);
        siz[num]+=siz[i];
    }
}
bool ch[200010];
int get_centroid(int num, int par, int sz){
    bool flag=true;
    for(auto i:link[num]){
        if(ch[i])continue;
        if(siz[i]>sz/2)flag=false;
    }
    if(flag)return num;
    for(auto i:link[num]){
        if(i==par||ch[i])continue;
        int temp=siz[i];
        siz[num]=sz-siz[i];
        siz[i]=sz;
        int ret=get_centroid(i, num, sz);
        if(ret)return ret;
        siz[num]=sz;
        siz[i]=temp;
    }
    return 0;
}
int ans=inf, p[200010];
vector<int> vc[200010], tmp;
void dfs2(int num, int par){
    p[num]=par;
    tmp.eb(col[num]);
    vc[col[num]].eb(num);
    for(auto i:link[num]){
        if(i==par||ch[i])continue;
        dfs2(i, num);
    }
}
int que[200010], re, fr;
bool ch2[200010];
void make_centroidtree(int num, int par){
    int cen=get_centroid(num, 0, siz[num]), ret=0; re=0;
    ch[cen]=true;
    dfs2(cen, 0);
    if(vc[col[cen]].size()!=vcm[col[cen]].size())ret=inf;
    for(auto i:vc[col[cen]])que[++re]=i;
    ch2[col[cen]]=true;
    for(fr=1; fr<=re; fr++){
        if(ch2[col[p[que[fr]]]])continue;
        ch2[col[p[que[fr]]]]=true;
        if(vc[col[p[que[fr]]]].size()!=vcm[col[p[que[fr]]]].size())ret=inf;
        for(auto i:vc[col[p[que[fr]]]])que[++re]=i;
        ret++;
    }
    ans=min(ans, ret);
    for(auto i:tmp){
        ch2[i]=false;
        vc[i].clear();
    }
  	tmp.clear();
    for(auto i:link[cen]){
        if(!ch[i])make_centroidtree(i, cen);
    }
}
int main(){
    scanf("%d %d", &n, &k);
    ch2[0]=true;
    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]);
    dfs(1, 0);
    make_centroidtree(1, 0);
    printf("%d", ans);
}

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
capital_city.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
capital_city.cpp:83: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: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59