Submission #64873

#	Time	Username	Problem	Language	Result	Execution time	Memory
64873		gs18115	족보 (KOI18_family)	C++14	44 / 100	3075 ms	30532 KiB

family

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=3e5+10;
vector<int>adj1[MAXN],adj2[MAXN];
vector<int>v1[MAXN],v2[MAXN];
bool vi[MAXN];
int N1,N2,K,i,j;
int pa1[MAXN],pa2[MAXN];
int chk[MAXN];
int cnt;
int csize(vector<int>V1,vector<int>V2)
{
    cnt++;
    int i;
    for(i=0;i<V1.size();i++)
        chk[V1[i]]=cnt;
    int c=0;
    for(i=0;i<V2.size();i++)
        if(chk[V2[i]]==cnt)
            c++;
    return c;
}
void pc1(int h,int s)
{
    adj1[pa1[h]].push_back(h);
    if(vi[h])
        return;
    vi[h]=true;
    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;
    if(pa2[h]!=-1)
        pc2(pa2[h],s);
    return;
}
void pc3(int h,int t)
{
    v1[h].push_back(t);
    if(pa1[h]!=-1)
        pc3(pa1[h],t);
    return;
}
void pc4(int h,int t)
{
    v2[h].push_back(t);
    if(pa2[h]!=-1)
        pc4(pa2[h],t);
    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);
    for(i=0;i<K;i++)
        pc3(i,i);
    for(i=0;i<K;i++)
        pc4(i,i);
    for(i=0;i<N1;i++)
    {
        for(j=0;j<N2;j++)
        {
            int co=csize(v1[i],v2[j]);
            if(co>0&&co!=min(v1[i].size(),v2[j].size()))
                return cout<<"NO",0;
        }
    }
    cout<<"YES";
    return 0;
}

Compilation message (stderr)

family.cpp: In function 'int csize(std::vector<int>, std::vector<int>)':
family.cpp:17:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<V1.size();i++)
             ~^~~~~~~~~~
family.cpp:20:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<V2.size();i++)
             ~^~~~~~~~~~
family.cpp: In function 'int main()':
family.cpp:90:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(co>0&&co!=min(v1[i].size(),v2[j].size()))
                      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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