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> a[MX];
vector<int> b[MX];
int aa[MX];
int bb[MX];
int sa[MX];
int sb[MX];
int s[MX];
int p[MX];
vector<pair<int,int>> c;
void dfs1(int v){
for(auto u: a[v]){
dfs1(u);
sa[v]+=sa[u];
aa[v]=aa[u];
}
if(a[v].size()==0){
aa[v]=v;
sa[v]=1;
}
c.push_back({sa[v],v});
}
void dfs2(int v){
for(auto u: b[v]){
dfs2(u);
sb[v]+=sb[u];
bb[v]=bb[u];
}
if(b[v].size()==0){
bb[v]=v;
sb[v]=1;
}
c.push_back({sb[v],-v});
}
int f(int x){
return x==p[x] ? x:p[x]=f(p[x]);
}
void U(int x,int y){
int xx=f(x);
int yy=f(y);
if(xx==yy)return;
p[xx]=yy;
s[yy]+=s[xx];
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>N1>>N2>>k;
n=max(N1,N2);
int i,j;
int r1,r2;
for(i=1 ; i<=N1 ; i++){
int p;
cin>>p;
if(p)
a[p].push_back(i);
else
r1=i;
}
for(i=1 ; i<=N2 ; i++){
int p;
cin>>p;
if(p)
b[p].push_back(i);
else
r2=i;
}
dfs1(r1);
dfs2(r2);
sort(c.begin(),c.end());
for(i=1 ; i<=k ;i++)p[i]=i,s[i]=1;
for(auto x: c){
int v=x.second;
if(v>0){
if(a[v].size()==0)continue;
int q=aa[*a[v].begin()];
for(auto u: a[v]){
U(q,aa[u]);
}
if(s[f(q)]!=sa[v]){
cout<<"NO";
return 0;
}
}
else{
v=-v;
if(b[v].size()==0)continue;
int q=bb[*b[v].begin()];
for(auto u: b[v]){
U(q,bb[u]);
}
if(s[f(q)]!=sb[v]){
cout<<"NO";
return 0;
}
}
}
cout<<"YES";
return 0;
}
Compilation message (stderr)
family.cpp: In function 'int main()':
family.cpp:55:11: warning: unused variable 'j' [-Wunused-variable]
55 | int i,j;
| ^
family.cpp:76:9: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
76 | dfs2(r2);
| ~~~~^~~~
family.cpp:75:9: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
75 | dfs1(r1);
| ~~~~^~~~
# | 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... |