oj.uz

Submission #251207

# Submission time Handle Problem Language Result Execution time Memory
251207 2020-07-20T15:20:09 Z teee None (KOI18_family) C++14
0 / 100
 9 ms 14464 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int par[300'010];
int sz[300'010];
int kk;
int find(int n){
    return par[n]?par[n]=find(par[n]):n;
}
void merge(int a,int b){
    a=find(a);
    b=find(b);
    if(a^b){
        sz[a]+=sz[b];
        par[b]=a;
    }
}
vector<int> v[2][300'010];
vector<pair<int,vector<int>>> check;
pair<int,int> dfs(int n,int idx){
    if(n<=kk)return {1,n};
    int cnt=0;
    vector<int> t;
    int c=0;
    for(auto i:v[idx][n]){
        pair<int,int> k=dfs(i,idx);
        if(k.first>0) {
            cnt += k.first;
            t.push_back(k.second);
            c = k.second;
        }
    }
    if(cnt>1)check.emplace_back(cnt,t);
    return {cnt,c};
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n1,n2,a;
    cin>>n1>>n2>>kk;
    fill(sz,sz+kk+1,1);
    for(int i=1;i<=n1;i++){
        cin>>a;
        v[0][a].push_back(i);
    }
    for(int i=1;i<=n2;i++){
        cin>>a;
        v[1][a].push_back(i);
    }
    dfs(v[0][0][0],0);
    dfs(v[1][0][0],1);
    sort(check.begin(),check.end());
    for(const auto& i:check){
        vector<int> t=i.second;
        int cnt=i.first;
        int p=find(t[0]);
        for(auto j:t){
            merge(p,j);
        }
        if(sz[find(p)]!=cnt){
            cout<<"NO";return 0;
        }
    }
    cout<<"YES";
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 41.0

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