Submission #130369

#	Time	Username	Problem	Language	Result	Execution time	Memory
130369		red1108	족보 (KOI18_family)	C++17	0 / 100	15 ms	14456 KiB

family

#include <bits/stdc++.h>
using namespace std;
vector<int> tree[2][300010];
int par[300010], n1, n2, p, root1, root2;
int tsize[2][300010], sth[2][300010], siz[300010];
priority_queue<pair<int,pair<int,int>>> pq;
void dfs(int t, int x){
    if(x<=p) tsize[t][x]=1;
    if(x<=p) sth[t][x]=x;
    for(auto i:tree[t][x]){
        dfs(t, i);
        tsize[t][x]+=tsize[t][i];
        if(sth[t][i]<=p) sth[t][x]=sth[t][i];
    }
}
int findpar(int x){
    if(x==par[x]) return x;
    return par[x]=findpar(par[x]);
}
void hap(int x, int y){
    if(findpar(x)==findpar(y)) return ;
    siz[findpar(y)]+=siz[findpar(x)];
    par[findpar(x)]=findpar(y);
}
int main(){
    int i;
    scanf("%d %d %d", &n1, &n2, &p);
    for(i=1;i<=n1;i++){
        int a;
        scanf("%d", &a);
        tree[0][a].push_back(i);
        if(a==0) root1=i;
    }
    for(i=1;i<=n2;i++){
        int a;
        scanf("%d", &a);
        tree[1][a].push_back(i);
        if(a==0) root2=i;
    }
    for(i=1;i<=p;i++) {
        par[i]=i;
        siz[i]=1;
    }
    dfs(0,root1);
    dfs(1,root2);
    for(i=p+1;i<=n1;i++)
        pq.push(make_pair(-tsize[0][i],make_pair(0,i)));
    for(i=p+1;i<=n2;i++)
        pq.push(make_pair(-tsize[1][i],make_pair(1,i)));
    while(!pq.empty()){
        int x = pq.top().second.second;
        int t = pq.top().second.first;
        pq.pop();
        int fi=sth[t][tree[t][x][0]];
        for(auto i:tree[t][x]){
            hap(fi,sth[t][i]);
        }
        if(siz[findpar(fi)]!=tsize[t][x]){
            printf("NO");
            return 0;
        }
        //printf("(%d %d) = %d \n", t, x, tsize[t][x]);
    }
    printf("YES");
}

Compilation message (stderr)

family.cpp: In function 'int main()':
family.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n1, &n2, &p);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
family.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~
family.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 27
• Subtask 3: 0 / 15
• Subtask 4: 0 / 41