Submission #130372

#	Time	Username	Problem	Language	Result	Execution time	Memory
130372		red1108	족보 (KOI18_family)	C++17	100 / 100	584 ms	74512 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], depth[2][300010];
struct A{
    int siz, t, x, depth;
    bool operator <(const A c) const{
        if(c.siz==siz) return depth>c.depth;
        return siz<c.siz;
    }
};
vector<A> q;
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]){
        depth[t][i]=depth[t][x]+1;
        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++) q.push_back({tsize[0][i],0,i,depth[0][i]});
    for(i=p+1;i<=n2;i++) q.push_back({tsize[1][i],1,i,depth[1][i]});
    sort(q.begin(), q.end());
    for(auto j:q){
        int x = j.x;
        int t = j.t;
        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("YES");
}

Compilation message (stderr)

family.cpp: In function 'int main()':
family.cpp:35: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:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~
family.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~

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