제출 #217204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
217204		DodgeBallMan	수도 (JOI20_capital_city)	C++14	0 / 100	945 ms	37752 KiB

capital_city

#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 2e5 + 10;
int par[N], cc[N], sz[N], c[N], cnt[N], ans = 1e9, n, k;
bool chk[N];
vector<int> col[N], g[N];
queue<int> q;

int getsz( int u, int p ) { sz[u] = 1; for( int v : g[u] ) if( v != p && !chk[v] ) sz[u] += getsz( v, u ); return sz[u]; }

int findcen( int u, int p, int all, pii &ret ) {
    //printf("cen : %d\n",u);
    int mx = all - sz[u];
    for( int v : g[u] ) if( v != p && !chk[v] ) 
        mx = max( mx, findcen( v, u, all, ret ) );
    ret = min( ret, pii( mx, u ) );
    return sz[u];
}

void dfs( int u, int p, bool fill ) {
    if( fill ) col[c[u]].emplace_back( u ), par[u] = p;
    else col[c[u]].clear(), cc[c[u]] = false;
    for( int v : g[u] ) if( v != p && !chk[v] ) dfs( v, u, fill ); 
}

void centroid( int u ) {
    //printf("%d ",u);
    pii ret( 1e9, -1 );
    getsz( u, u );
    findcen( u, u, sz[u], ret );
    dfs( u, u, true );
    bool check = true;
    u = ret.y;
    //printf("CEN : %d\n",u);
    int cou = 1;
    q.emplace( c[u] ), cc[c[u]] = true;
    while( !q.empty() ) {
        int now = q.front(); q.pop();
        if( col[now].size() != cnt[now] ) { 
            check = false;
            break ;
        }
        for( int x : col[now] ) if( x != u && !cc[c[par[x]]] ) {
            cc[c[par[x]]] = true;
            cou++;
            q.emplace( c[par[x]] );
        }
    }
    while( !q.empty() ) q.pop();
    if( check ) ans = min( ans, cou );
    dfs( u, u, false ), chk[u] = true;
    for( int v : g[u] ) if( !chk[v] ) centroid( v );

}

int main()
{
    scanf("%d %d",&n,&k);
    for( int i = 1, a, b ; i < n ; i++ ) {
        scanf("%d %d",&a,&b);
        g[a].emplace_back( b ), g[b].emplace_back( a );
    }
    for( int i = 1 ; i <= n ; i++ ) {
        scanf("%d",&c[i]);
        cnt[c[i]]++;
    }
    centroid( 1 );
    printf("%d",ans-1);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

capital_city.cpp: In function 'void centroid(int)':
capital_city.cpp:44:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if( col[now].size() != cnt[now] ) { 
             ~~~~~~~~~~~~~~~~^~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:63: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:65: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:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&c[i]);
         ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59