oj.uz

답안 #716257

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
716257 2023-03-29T11:48:17 Z Ahmed57 Mergers (JOI19_mergers) C++14
0 / 100
 137 ms 18824 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.first]==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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4952 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Incorrect 3 ms 4948 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4952 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Incorrect 3 ms 4948 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4952 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Incorrect 3 ms 4948 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 8956 KB Output is correct
2 Correct 137 ms 18824 KB Output is correct
3 Incorrect 10 ms 5340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4952 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Incorrect 3 ms 4948 KB Output isn't correct
15 Halted 0 ms 0 KB -