oj.uz

Submission #716248

# Submission time Handle Problem Language Result Execution time Memory
716248 2023-03-29T11:32:23 Z Ahmed57 Mergers (JOI19_mergers) C++14
0 / 100
 118 ms 18768 KB 
#include <bits/stdc++.h>

using namespace std;
vector<int> adj[200001];
int arr[200001] , cnt[200001];
bool mark[200001];
pair<int,map<int,int>> dfs(int i,int pr){
    map<int,int> mp;
    pair<int,map<int,int>> p1;
    int bad = 0;
    mp[arr[i]]++;
    if(cnt[arr[i]]!=1)bad++;
    for(auto j:adj[i]){
        if(j!=pr){
            p1 = dfs(j,i);
            bad+=p1.first;
            if(p1.second.size()>mp.size())swap(mp,p1.second);
            for(auto k:p1.second){
                if(mp[k.first]!=0)bad--;
                mp[k.first]+=k.second;
                if(mp[k.second]==cnt[k.first]&&k.second!=cnt[k.first])bad--;
            }
        }
    }
    if(bad==0){
        mark[i] = 1;
    }
    return {bad,mp};
}
int calc(int i,int pr){
    long long sum = 0;
    long long ma = 0;
    for(auto j:adj[i]){
        if(j==pr)continue;
        long long val = calc(j,i);
        sum+=val;
        ma = max(ma,val);
    }
    if(ma>sum-ma){
        return ma;
    }else{
        return (sum/2)+(mark[i]||sum%2);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i = 0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
        cnt[arr[i]]++;
    }
    pair<int,map<int,int>> nothing = dfs(1,0);
    mark[1] = 0;
    cout<<calc(1,0)<<"\n";
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8968 KB Output is correct
2 Correct 118 ms 18768 KB Output is correct
3 Incorrect 8 ms 5348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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