oj.uz

답안 #240329

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
240329 2020-06-19T10:31:44 Z mhy908 수도 (JOI20_capital_city) C++14
0 / 100
 1426 ms 44524 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[num]]!=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[num]]!=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;
    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[num]]!=vcm[col[cen]].size())ret=inf;
        ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:60:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(cnt[col[num]]!=vcm[col[p[que[fr]]]].size())ret=inf;
            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:72: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:76: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:80: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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 652 ms 40704 KB Output is correct
2 Correct 236 ms 44524 KB Output is correct
3 Correct 632 ms 43912 KB Output is correct
4 Correct 240 ms 44496 KB Output is correct
5 Incorrect 1426 ms 41440 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -