oj.uz

Submission #240253

# Submission time Handle Problem Language Result Execution time Memory
240253 2020-06-19T03:21:06 Z mhy908 Capital City (JOI20_capital_city) C++14
0 / 100
 3000 ms 60432 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19968 KB Output is correct
2 Correct 18 ms 19840 KB Output is correct
3 Correct 18 ms 20088 KB Output is correct
4 Correct 16 ms 19968 KB Output is correct
5 Correct 18 ms 19968 KB Output is correct
6 Correct 18 ms 19968 KB Output is correct
7 Incorrect 19 ms 19968 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19968 KB Output is correct
2 Correct 18 ms 19840 KB Output is correct
3 Correct 18 ms 20088 KB Output is correct
4 Correct 16 ms 19968 KB Output is correct
5 Correct 18 ms 19968 KB Output is correct
6 Correct 18 ms 19968 KB Output is correct
7 Incorrect 19 ms 19968 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3072 ms 60432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19968 KB Output is correct
2 Correct 18 ms 19840 KB Output is correct
3 Correct 18 ms 20088 KB Output is correct
4 Correct 16 ms 19968 KB Output is correct
5 Correct 18 ms 19968 KB Output is correct
6 Correct 18 ms 19968 KB Output is correct
7 Incorrect 19 ms 19968 KB Output isn't correct
8 Halted 0 ms 0 KB -