oj.uz

Submission #817645

# Submission time Handle Problem Language Result Execution time Memory
817645 2023-08-09T14:24:34 Z LucaIlie Mergers (JOI19_mergers) C++17
0 / 100
 87 ms 16760 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX_N = 1e5;
int state[MAX_N + 1], depth[MAX_N + 1], parent[MAX_N + 1], preord[MAX_N + 1];
vector<int> edges[MAX_N + 1], cities[MAX_N + 1];
set<int> stateEdges[MAX_N + 1];
 
struct DSU {
    int comp;
    int p[MAX_N + 1];
 
    void init( int k ) {
        for ( int u = 1; u <= k; u++ )
            p[u] = u;
        comp = k;
    }
 
    int find( int u ) {
        if ( p[u] == u )
            return u;
        p[u] = find( p[u] );
        return p[u];
    }
 
    void merge( int u, int v ) {
        u = find( u );
        v = find( v );
        if ( u == v )
            return;
 
        comp--;
        p[u] = v;
    }
} dsu;
 
int pre = 0;
void dfs( int u, int p ) {
    parent[u] = p;
    depth[u] = depth[p] + 1;
    preord[u] = pre++;
    for ( int v: edges[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
    }
}
 
int main() {
    int n, k;
 
    cin >> n >> k;
    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back( v );
        edges[v].push_back( u );
    }
    for ( int u = 1; u <= n; u++ ) {
        cin >> state[u];
        cities[state[u]].push_back( u );
    }
 
    dfs( 1, 0 );
 
    dsu.init( k );
 
    for ( int u = 1; u <= n; u++ )
        state[u] = dsu.find( state[u] );
 
    for ( int u = 1; u <= n; u++ ) {
        for ( int v: edges[u] ) {
            if ( state[u] == state[v] )
                continue;
            stateEdges[state[u]].insert( state[v] );
            stateEdges[state[v]].insert( state[u] );
        }
    }
 
    int leafs = 0;
    for ( int s = 1; s <= k; s++ ) {
        if ( stateEdges[s].size() == 1 )
            leafs++;
    }
 
    cout << (leafs + 1) / 2;
 
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 30.0

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