oj.uz

Submission #130467

# Submission time Handle Problem Language Result Execution time Memory
130467 2019-07-15T09:17:08 Z DodgeBallMan Mergers (JOI19_mergers) C++14
0 / 100
 132 ms 33148 KB 
#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);
    e.reserve(n);
    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 );
                a = dsu[a] = find( par[a] );
            }
        }
    }
    for(auto &x : e) if(find(x.x) != find(x.y)) deg[x.x]++, deg[x.y]++;
    for( int i = 1 ; i <= n ; i++ ) if( deg[i] == 1 ) cnt++;
    printf("%d",( cnt + 1 ) / 2);
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:37:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int j = 1 ; j < co[i].size() ; j++ ) {
                          ~~^~~~~~~~~~~~~~
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:27: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:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&s);
         ~~~~~^~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 30184 KB Output is correct
2 Correct 132 ms 33148 KB Output is correct
3 Incorrect 29 ms 24056 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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