oj.uz

Submission #207629

# Submission time Handle Problem Language Result Execution time Memory
207629 2020-03-08T08:16:39 Z nvmdava Mergers (JOI19_mergers) C++17
0 / 100
 105 ms 45032 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 500005
#define MOD 1000000007
#define INF 0x3f3f3f3f

int col[N];
int cnt[N];
int dsu[N];
vector<pair<int, int> > e;
vector<int> adj[N];

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

void merge(int v, int u){
    v = find(v);
    u = find(u);
    dsu[v] = u;
}

map<int, int> in[N];

void dfs(int v, int p){
    if(cnt[col[v]] != 1)
        in[v][col[v]] = 1;
    for(auto& x: adj[v]){
        if(x == p) continue;
        dfs(x, v);
        if(in[x].size() > in[v].size())
            swap(in[x], in[v]);
    }
    for(auto& x : adj[v]){
        if(x == p) continue;
        for(auto& y : in[x]){
            if( (in[v][y.ff] += y.ss) == cnt[y.ff])
                in[v].erase(y.ff);
        }
    }
    if(!in[v].empty()){
        merge(col[v], col[p]);
    }
}

int deg[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin>>n>>k;
    for(int i = 1; i <= k; ++i)
        dsu[i] = i;
    for(int a, b, i = 1; i < n; ++i){
        cin>>a>>b;
        e.push_back({a, b});
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for(int i = 1; i <= n; ++i){
        cin>>col[i];
        ++cnt[col[i]];
    }

    dfs(1, 0);
    for(int i = 1; i <= n; ++i)
        col[i] = find(col[i]);
    
    for(auto& x : e){
        x.ff = col[x.ff];
        x.ss = col[x.ss];
        if(x.ff != x.ss){
            ++deg[x.ff];
            ++deg[x.ss];
        }
    }
    int ans = 0;
    for(int i = 1; i <= k; ++i)
        if(deg[i] == 1)
            ++ans;
    cout<<max(0, ans - 1);
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 45032 KB Output is correct
2 Incorrect 82 ms 41448 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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