Submission #403390

#	Time	Username	Problem	Language	Result	Execution time	Memory
403390		tqbfjotld	족보 (KOI18_family)	C++14	100 / 100	590 ms	65332 KiB

family

#include <bits/stdc++.h>
using namespace std;

int n1,n2,k;
vector<int> adjl1[300005];
vector<int> adjl2[300005];
int preord1[300005];
int someval[300005];
int finord[300005];
int cur = 1;
int root1,root2;
int min1[300005];
int max1[300005];
int min2[300005];
int max2[300005];
int numleaves1[300005];
int numleaves2[300005];

void dfs1(int node){
    preord1[node] = cur++;
    if (node<=k){
        numleaves1[node] = 1;
    }
    for (auto x : adjl1[node]){
        dfs1(x);
        numleaves1[node] += numleaves1[x];
    }
}

bool cmp(int a, int b){
    return someval[a]<someval[b];
}

void dfs2(int node){
    if (node<=k){
        someval[node] = preord1[node];
        numleaves2[node] = 1;
        return;
    }
    someval[node] = 999999999;
    for (auto x : adjl2[node]){
        dfs2(x);
        someval[node] = min(someval[node],someval[x]);
        numleaves2[node] += numleaves2[x];
    }
    sort(adjl2[node].begin(),adjl2[node].end(),cmp);
}

void dfs3(int node){
    if (node<=k)finord[node] = cur++;
    if (node<=k) {
        min2[node] = finord[node];
        max2[node] = finord[node];
    }
    else{
        min2[node] = 999999999;
        max2[node] = -1;
    }
    for (auto x : adjl2[node]){
        dfs3(x);
        min2[node] = min(min2[node],min2[x]);
        max2[node] = max(max2[node],max2[x]);
    }
}

void dfs4(int node){
    if (node<=k) {
        min1[node] = finord[node];
        max1[node] = finord[node];
    }
    else{
        min1[node] = 999999999;
        max1[node] = -1;
    }
    for (auto x : adjl1[node]){
        dfs4(x);
        min1[node] = min(min1[node],min1[x]);
        max1[node] = max(max1[node],max1[x]);
    }
}

bool cmp2(pair<int,int>a,pair<int,int>b){
    if (a.first<b.first) return true;
    if (a.first>b.first) return false;
    return a.second>b.second;
}

int main(){
    scanf("%d%d%d",&n1,&n2,&k);
    for (int x = 1; x<=n1; x++){
        int t;
        scanf("%d",&t);
        if (t!=0){
            adjl1[t].push_back(x);
        }
        else root1 = x;
    }
    for (int x = 1; x<=n2; x++){
        int t;
        scanf("%d",&t);
        if (t!=0){
            adjl2[t].push_back(x);
        }
        else root2 = x;
    }
    dfs1(root1);
    //printf("1\n");
    dfs2(root2);
    //printf("2\n");
    dfs3(root2);
    //printf("3\n");
    dfs4(root1);
    //printf("4\n");
    vector<pair<int,int> > stuff;
    for (int x = k+1; x<=n1; x++){
        stuff.push_back({min1[x],max1[x]});
        if (max1[x]-min1[x]+1!=numleaves1[x]){
            printf("NO");
            return 0;
        }
    }
    for (int x = k+1; x<=n2; x++){
        stuff.push_back({min2[x],max2[x]});
        if (max2[x]-min2[x]+1!=numleaves2[x]){
            printf("NO");
            return 0;
        }
    }
    sort(stuff.begin(),stuff.end(),cmp2);
    stack<int> ends;
    for (auto x : stuff){
        while (!ends.empty() && ends.top()<x.first)ends.pop();
        if (ends.empty() || x.second<=ends.top()){
            ends.push(x.second);
        }
        else{
            printf("NO");
            return 0;
        }
    }
    printf("YES");
}

Compilation message (stderr)

family.cpp: In function 'int main()':
family.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d%d%d",&n1,&n2,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
family.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~
family.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~

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