oj.uz

Submission #817706

# Submission time Handle Problem Language Result Execution time Memory
817706 2023-08-09T15:11:00 Z LucaIlie Mergers (JOI19_mergers) C++17
0 / 100
 185 ms 102592 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e5;
const int MAX_LOG_N = 19;
int state[MAX_N + 1], parent[MAX_LOG_N + 1][MAX_N + 1], depth[MAX_N + 1], uplus[MAX_N + 1], uminus[MAX_N + 1];
vector<int> edges[MAX_N + 1], cities[MAX_N + 1];
set<int> stateEdges[MAX_N + 1];

struct DSU {
    int p[MAX_N + 1];

    void init( int k ) {
        for ( int u = 1; u <= k; u++ )
            p[u] = u;
    }

    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;

        p[u] = v;
    }
} dsu;

void dfs( int u, int p ) {
    depth[u] = depth[p] + 1;
    parent[0][u] = p;
    for ( int v: edges[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
    }
}

void init() {
    for ( int p = 1; p <= MAX_LOG_N; p++ ) {
        for ( int u = 0; u <= MAX_N; u++ )
            parent[p][u] = parent[p - 1][parent[p - 1][u]];
    }
}

int ancestor( int u, int d ) {
    for ( int p = MAX_LOG_N; p >= 0; p-- ) {
        if ( d >= (1 << p) ) {
            d -= (1 << p);
            u = parent[p][u];
        }
    }

    return u;
}

int lca( int u, int v ) {
    if ( depth[u] > depth[v] )
        swap( u, v );
    for ( int p = MAX_LOG_N; p >= 0; p-- ) {
        if ( depth[parent[p][v]] >= depth[u] )
            v = parent[p][v];
    }

    if ( u == v )
        return u;

    for ( int p = MAX_LOG_N; p >= 0; p-- ) {
        if ( parent[p][u] != parent[p][v] ) {
            u = parent[p][u];
            v = parent[p][v];
        }
    }

    return parent[0][u];
}

void dfsMerge( int u, int p, int upd ) {
    upd += uplus[u];

    if ( upd > 0 )
        dsu.merge( state[u], state[parent[0][u]] );

    for ( int v: edges[u] ) {
        if ( v == p )
            continue;
        dfsMerge( v, u, upd + uminus[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 );

    init();
    for ( int s = 1; s <= k; s++ ) {
        for ( int i = 0; i < cities[s].size() - 1; i++ ) {
            int u = cities[s][i], v = cities[s][i + 1];
            int l = lca( u, v );
            int w = ancestor( u, depth[u] - depth[l] - 1);
            int t = ancestor( v, depth[v] - depth[l] - 1);
            if ( l == u ) {
                uplus[t]++;
                uminus[v]--;
            }
            else if ( l == v ) {
                uplus[w]++;
                uminus[u]--;
            }
            else {
                uplus[w]++;
                uminus[u]--;
                uplus[t]++;
                uminus[v]--;
            }
        }
    }

    dsu.init( k );
    dfsMerge( 1, 0, 0 );
    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;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:117:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for ( int i = 0; i < cities[s].size() - 1; i++ ) {
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 90936 KB Output is correct
2 Correct 185 ms 102592 KB Output is correct
3 Incorrect 47 ms 84872 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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