Submission #251207

#	Time	Username	Problem	Language	Result	Execution time	Memory
251207		teee	족보 (KOI18_family)	C++14	0 / 100	9 ms	14464 KiB

family

#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
• Subtask 2: 0 / 27
• Subtask 3: 0 / 15
• Subtask 4: 0 / 41