oj.uz

Submission #217204

# Submission time Handle Problem Language Result Execution time Memory
217204 2020-03-29T08:43:21 Z DodgeBallMan Capital City (JOI20_capital_city) C++14
0 / 100
 945 ms 37752 KB 
#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;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Incorrect 9 ms 9728 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Incorrect 9 ms 9728 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 945 ms 37752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Incorrect 9 ms 9728 KB Output isn't correct
5 Halted 0 ms 0 KB -