oj.uz

답안 #716255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
716255 2023-03-29T11:41:06 Z Ahmed57 Mergers (JOI19_mergers) C++14
0 / 100
 122 ms 18868 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){
    int sum = 0;
    for(auto j:adj[i]){
        if(j==pr)continue;
        sum+=calc(j,i);
    }
    if(mark[i]){
        if(sum)return sum;
        else return 1;
    }else return sum;
}
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)+1)/2<<"\n";
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 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 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5032 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Incorrect 3 ms 5028 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 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 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5032 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Incorrect 3 ms 5028 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 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 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5032 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Incorrect 3 ms 5028 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 8900 KB Output is correct
2 Incorrect 122 ms 18868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 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 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5032 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Incorrect 3 ms 5028 KB Output isn't correct
17 Halted 0 ms 0 KB -