oj.uz

Submission #303048

# Submission time Handle Problem Language Result Execution time Memory
303048 2020-09-19T19:31:08 Z knon0501 None (KOI18_family) C++14
0 / 100
 1 ms 640 KB 
#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

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);
      |     ~~~~^~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Incorrect 1 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Incorrect 1 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Incorrect 1 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Incorrect 1 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -