Submission #240253

#	Time	Username	Problem	Language	Result	Execution time	Memory
240253		mhy908	Capital City (JOI20_capital_city)	C++14	0 / 100	3072 ms	60432 KiB

capital_city

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long LL;
struct UNION_FIND{
    int par[200010];
    UNION_FIND(){for(int i=1; i<=200000; i++)par[i]=i;}
    int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);}
    void mergepar(int a, int b){par[findpar(a)]=findpar(b);}
}uf;
int n, k, col[200010], siz[200010];
vector<int> link[200010];
void dfs(int num, int par){
    siz[num]=1;
    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;
}
vector<int> ans[200010];
set<int> cnum, s[200010];
void dfs2(int num, int par, int c){
    s[col[num]].insert(c);
    cnum.insert(col[num]);
    for(auto i:link[num]){
        if(i==par)continue;
        dfs2(i, num, c);
    }
}
int u[200010];
void make_centroidtree(int num, int par){
    int cen=get_centroid(num, 0, siz[num]), c=0;
    ch[cen]=true;
    for(auto i:link[cen]){
        //if(ch[i])continue;
        dfs2(i, cen, ++c);
    }
    for(auto i:cnum){
        if(s[i].size()>=2&&i!=col[cen])ans[i].eb(col[cen]);
        s[i].clear();
    }
    cnum.clear();
    for(auto i:link[cen]){
        if(ch[i])continue;
        make_centroidtree(i, cen);
    }
}
int anss;
bool ch2[200010];
void dfs3(int num){
    anss++;
    ch2[num]=true;
    for(auto i:ans[num]){
        if(!ch2[i])dfs3(i);
    }
}
int main(){
    scanf("%d %d", &n, &k);
    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);
    dfs3(1);
    printf("%d", anss-1);
}

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:79: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:82: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:86: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: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59