Submission #64872

#	Time	Username	Problem	Language	Result	Execution time	Memory
64872		gs18115	족보 (KOI18_family)	C++14	0 / 100	15 ms	14484 KiB

family

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=3e5+10;
vector<int>adj1[MAXN],adj2[MAXN];
bool vi[MAXN];
int N1,N2,K,i,j;
int pa1[MAXN],pa2[MAXN];
int S1[MAXN],E1[MAXN],S2[MAXN],E2[MAXN];
void pc1(int h,int s)
{
    adj1[pa1[h]].push_back(h);
    if(vi[h])
        return;
    vi[h]=true;
    S1[h]=s;
    if(pa1[h]!=-1)
        pc1(pa1[h],s);
    return;
}
void pc2(int h,int s)
{
    adj2[pa2[h]].push_back(h);
    if(vi[h])
        return;
    vi[h]=true;
    S2[h]=s;
    if(pa2[h]!=-1)
        pc2(pa2[h],s);
}
void pc3(int h,int e)
{
    if(vi[h])
        return;
    vi[h]=true;
    E1[h]=e;
    if(pa1[h]!=-1)
        pc3(pa1[h],e);
    return;
}
void pc4(int h,int e)
{
    if(vi[h])
        return;
    vi[h]=true;
    E2[h]=e;
    if(pa2[h]!=-1)
        pc4(pa2[h],e);
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>N1>>N2>>K;
    for(i=0;i<N1;i++)
    {
        cin>>pa1[i];
        pa1[i]--;
    }
    for(i=0;i<N2;i++)
    {
        cin>>pa2[i];
        pa2[i]--;
    }
    fill(vi,vi+N1,false);
    for(i=0;i<K;i++)
        pc1(i,i);
    fill(vi,vi+N2,false);
    for(i=0;i<K;i++)
        pc2(i,i);
    fill(vi,vi+N1,false);
    for(i=K;i-->0;)
        pc3(i,i);
    fill(vi,vi+N2,false);
    for(i=K;i-->0;)
        pc4(i,i);
    for(i=0;i<N1;i++)
        for(j=0;j<N2;j++)
            if(min(E1[i],E2[j])-max(S1[i],S2[j])>=0&&min(E1[i],E2[j])-max(S1[i],S2[j])!=min(E1[i]-S1[i],E2[j]-S2[j]))
                return cout<<"NO",0;
    cout<<"YES";
    return 0;
}

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