Submission #217218

#	Time	Username	Problem	Language	Result	Execution time	Memory
217218		DodgeBallMan	Capital City (JOI20_capital_city)	C++14	100 / 100	1167 ms	38264 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, int &ret) {
    int mx = all - sz[u];
    for(int v : g[u]) if(v != p && !chk[v])
        mx = max(mx, findcen(v, u, all, ret));
    if(mx <= (all + 1) / 2) ret = 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(), par[u] = -1, 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], u );
    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\n",ans-1);
    return 0;
}   

Compilation message (stderr)

capital_city.cpp: In function 'void centroid(int)':
capital_city.cpp:42: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:61: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:63: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:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&c[i]);
         ~~~~~^~~~~~~~~~~~

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