oj.uz

답안 #64872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
64872 2018-08-06T01:30:20 Z gs18115 족보 (KOI18_family) C++14
0 / 100
 15 ms 14484 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Incorrect 14 ms 14484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Incorrect 14 ms 14484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Incorrect 14 ms 14484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Incorrect 14 ms 14484 KB Output isn't correct
3 Halted 0 ms 0 KB -