oj.uz

Submission #240330

# Submission time Handle Problem Language Result Execution time Memory
240330 2020-06-19T10:34:04 Z mhy908 Capital City (JOI20_capital_city) C++14
1 / 100
 3000 ms 44544 KB 
#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], cnt[200010];
vector<int> vc[200010], tmp;
void dfs2(int num, int par){
    p[num]=par;
    tmp.eb(col[num]);
    cnt[col[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(cnt[col[cen]]!=vcm[col[cen]].size())ret=inf;
    for(auto i:vcm[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(cnt[col[p[que[fr]]]]!=vcm[col[p[que[fr]]]].size())ret=inf;
        for(auto i:vcm[col[p[que[fr]]]])que[++re]=i;
        ret++;
    }
    ans=min(ans, ret);
    for(auto i:tmp){
        ch2[i]=false;
        cnt[i]=0;
    }
    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

capital_city.cpp: In function 'void make_centroidtree(int, int)':
capital_city.cpp:54:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(cnt[col[cen]]!=vcm[col[cen]].size())ret=inf;
        ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:60:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(cnt[col[p[que[fr]]]]!=vcm[col[p[que[fr]]]].size())ret=inf;
            ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 14 ms 14464 KB Output is correct
3 Correct 15 ms 14464 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct
6 Correct 13 ms 14464 KB Output is correct
7 Correct 14 ms 14464 KB Output is correct
8 Correct 13 ms 14464 KB Output is correct
9 Correct 15 ms 14464 KB Output is correct
10 Correct 13 ms 14464 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 14 ms 14464 KB Output is correct
3 Correct 15 ms 14464 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct
6 Correct 13 ms 14464 KB Output is correct
7 Correct 14 ms 14464 KB Output is correct
8 Correct 13 ms 14464 KB Output is correct
9 Correct 15 ms 14464 KB Output is correct
10 Correct 13 ms 14464 KB Output is correct
11 Correct 17 ms 14592 KB Output is correct
12 Correct 15 ms 14592 KB Output is correct
13 Correct 15 ms 14592 KB Output is correct
14 Correct 15 ms 14592 KB Output is correct
15 Correct 15 ms 14592 KB Output is correct
16 Incorrect 17 ms 14592 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 40556 KB Output is correct
2 Correct 234 ms 40808 KB Output is correct
3 Correct 640 ms 40336 KB Output is correct
4 Correct 253 ms 40808 KB Output is correct
5 Correct 1460 ms 37744 KB Output is correct
6 Correct 283 ms 44544 KB Output is correct
7 Execution timed out 3086 ms 41708 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 14 ms 14464 KB Output is correct
3 Correct 15 ms 14464 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct
6 Correct 13 ms 14464 KB Output is correct
7 Correct 14 ms 14464 KB Output is correct
8 Correct 13 ms 14464 KB Output is correct
9 Correct 15 ms 14464 KB Output is correct
10 Correct 13 ms 14464 KB Output is correct
11 Correct 17 ms 14592 KB Output is correct
12 Correct 15 ms 14592 KB Output is correct
13 Correct 15 ms 14592 KB Output is correct
14 Correct 15 ms 14592 KB Output is correct
15 Correct 15 ms 14592 KB Output is correct
16 Incorrect 17 ms 14592 KB Output isn't correct
17 Halted 0 ms 0 KB -