This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)];
}
}
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |