oj.uz

답안 #817529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817529 2023-08-09T13:17:50 Z LucaIlie Mergers (JOI19_mergers) C++17
0 / 100
 84 ms 13536 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], dp[MAX_N + 1], stateGrad[MAX_N + 1];
vector<int> edges[MAX_N + 1], cities[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;

void dfs( int u, int p ) {
    parent[u] = p;
    depth[u] = depth[p] + 1;
    for ( int v: edges[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
    }
}
void calcDP( int u, int p ) {
    set<int> s;
    s.insert( state[u] );
    for ( int v: edges[u] ) {
        if ( v == p )
            continue;

        calcDP( v, u );
        dp[u] += dp[v];
        s.insert( state[v] );
    }
    dp[u] += s.size() / 2;
    printf( "%d %d %d %d\n", u, dp[u], s.size(), state[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 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];
            while ( depth[u] > depth[v] ) {
                dsu.merge( state[u], state[parent[u]] );
                u = parent[u];
            }
            while ( depth[v] > depth[u] ) {
                dsu.merge( state[v], state[parent[v]] );
                v = parent[v];
            }
            while ( u != v ) {
                dsu.merge( state[u], state[parent[u]] );
                u = parent[u];
                dsu.merge( state[v], state[parent[v]] );
                v = parent[v];
            }
        }
    }

    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] )
            stateGrad[state[v]]++;
    }

    int leafs = 0;
    for ( int s = 1; s <= k; s++ ) {
        if ( stateGrad[s] == 1 )
            leafs++;
    }
    cout << (leafs == 0 ? 0 : leafs - 1);

    return 0;
}

Compilation message

mergers.cpp: In function 'void calcDP(int, int)':
mergers.cpp:58:21: warning: format '%d' expects argument of type 'int', but argument 4 has type 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   58 |     printf( "%d %d %d %d\n", u, dp[u], s.size(), state[u] );
      |                    ~^                  ~~~~~~~~
      |                     |                        |
      |                     int                      std::set<int>::size_type {aka long unsigned int}
      |                    %ld
mergers.cpp: In function 'int main()':
mergers.cpp:80:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for ( int i = 0; i < cities[s].size() - 1; i++ ) {
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 10232 KB Output is correct
2 Incorrect 78 ms 13536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -