Submission #300363

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

family

#include <bits/stdc++.h>
using namespace std;
const int MX=3e5+5;
int n,k;
int N1,N2;

struct Tree{

vector<int> a[MX];
int dth[MX];
int p[MX][20];
int r;
int lca(int v,int u){
    int i,j;

    if(dth[v]>dth[u])swap(u,v);
    for(i=19 ; i>=0 ; i--)if(dth[u]-dth[v]>=(1<<i))u=p[u][i];
    if(u==v)return v;
    for(i=19 ; i>=0 ; i--){
        if(p[u][i]!=p[v][i]){
            u=p[u][i];
            v=p[v][i];
        }
    }
    return p[v][0];
}
void dfs(int v){
    for(auto u: a[v]){
        if(dth[u])continue;
        p[u][0]=v;
        dth[u]=dth[v]+1;
        dfs(u);
    }
}

void build(){
    dth[1]=1;
    dfs(r);
    for(int i=1 ; i<20 ; i++){
        for(int j=1 ; j<=n ; j++){
            p[j][i]=p[p[j][i-1]][i-1];
        }
    }
}

void add(int u,int v){
    a[u].push_back(v);
}
};

Tree T1,T2;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>N1>>N2>>k;
    n=max(N1,N2);
    int i,j;

    for(i=1 ; i<=N1 ; i++){
        int p;
        cin>>p;
        if(p){
            T1.add(p,i);
        }
        else
            T1.r=i;
    }
    for(i=1 ; i<=N2  ; i++){
        int p;
        cin>>p;
        if(p){
            T2.add(p,i);
        }
        else
            T2.r=i;
    }
    T1.build();
    T2.build();
    for(i=1 ; i<=k ; i++){
        for(j=1 ; j<=k ; j++){
            for(int l=1 ; l<=k ; l++){
                int u=T1.lca(i,j);
                int v=T1.lca(j,l);
                int q=T2.lca(i,j);
                int w=T2.lca(j,l);
               /// cout<<i<<" "<<j<<" "<<l<<" "<<u<<" "<<v<<" "<<q<<" "<<w<<endl;
                if(T1.dth[u]<T1.dth[v] && T2.dth[q]>T2.dth[w]){
                    cout<<"NO";
                    return 0;
                }
            }
        }
    }
    cout<<"YES";
    return 0;
}

Compilation message (stderr)

family.cpp: In member function 'int Tree::lca(int, int)':
family.cpp:14:11: warning: unused variable 'j' [-Wunused-variable]
   14 |     int i,j;
      |           ^

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