Submission #130465

#	Time	Username	Problem	Language	Result	Execution time	Memory
130465		DodgeBallMan	Mergers (JOI19_mergers)	C++14	100 / 100	895 ms	91100 KiB

mergers

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

using namespace std;

const int N = 5e5 + 10;

int par[N], dep[N], dsu[N], deg[N], n, k, cnt;
vector<int> g[N], co[N];
vector<pii> e;

void pre( int now, int p ) {
    par[now] = p, dep[now] = dep[p] + 1;
    for( int i : g[now] ) if( i != p ) pre( i, now );
}

int find( int now ) { return dsu[now] = dsu[now] == now ? now : find( dsu[now] ); }

int main()
{
    scanf("%d %d",&n,&k);
    for( int i = 1 ; i <= n ; i++ ) dsu[i] = i;
    for( int i = 1, u, v ; i <= n - 1 ; i++ ) {
        scanf("%d %d",&u,&v);
        g[u].emplace_back( v ), g[v].emplace_back( u );
        e.emplace_back( pii( u, v ) ); 
    }
    for( int i = 1, s ; i <= n ; i++ ) {
        scanf("%d",&s);
        co[s].emplace_back( i );
    }
    pre( 1, 0 );
    for( int i = 1 ; i <= k ; i++ ) if( co[i].size() > 1 ) {
        for( int j = 1 ; j < co[i].size() ; j++ ) {
            int a = find( co[i][j] ), b = find( co[i][j-1] );
            while( a != b ) {
                if( dep[a] < dep[b] ) swap( a, b );
                dsu[a] = find( par[a] );
                a = dsu[a];
            }
        }
    }
    for( int i = 0 ; i < e.size() ; i++ ) {
        int a = find( e[i].x ), b = find( e[i].y );
        if( a != b ) deg[a]++, deg[b]++;
    } 
    for( int i = 1 ; i <= n ; i++ ) if( deg[i] == 1 ) cnt++;
    printf("%d",( cnt + 1 ) >> 1 );
    return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:36:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int j = 1 ; j < co[i].size() ; j++ ) {
                          ~~^~~~~~~~~~~~~~
mergers.cpp:45:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = 0 ; i < e.size() ; i++ ) {
                      ~~^~~~~~~~~~
mergers.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~
mergers.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&u,&v);
         ~~~~~^~~~~~~~~~~~~~~
mergers.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&s);
         ~~~~~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30