Submission #300421

#TimeUsernameProblemLanguageResultExecution timeMemory
300421knon0501족보 (KOI18_family)C++14
44 / 100
2948 ms191048 KiB
#include <bits/stdc++.h> using namespace std; const int MX=5e3+5; int n,k; int N1,N2; vector<int> v[MX]; int lca1[MX][MX]; int lca2[MX][MX]; 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[r]=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=i ; j<=k ; j++){ lca1[i][j]=lca1[j][i]=T1.dth[T1.lca(i,j)]; lca2[i][j]=lca2[j][i]=T2.dth[T2.lca(i,j)]; } } if(n>=5000)return 0; for(i=1 ; i<=k ; i++){ int mx=0; for(j=1 ; j<=n ; j++) v[j].clear(); for(j=1 ; j<=k ; j++){ v[lca1[i][j]].push_back(j); } int l=0; for(j=1 ; j<=n ; j++){ for(auto x: v[j-1]){ mx=max(mx,lca2[i][x]); l++; } for(auto x: v[j]){ if(mx>lca2[i][x]){ cout<<"NO"; return 0; } } } } cout<<"YES"; return 0; }

Compilation message (stderr)

family.cpp: In member function 'int Tree::lca(int, int)':
family.cpp:16:11: warning: unused variable 'j' [-Wunused-variable]
   16 |     int i,j;
      |           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...