Submission #64874

#	Time	Username	Problem	Language	Result	Execution time	Memory
64874		gs18115	족보 (KOI18_family)	C++14	44 / 100	3048 ms	30464 KiB

family

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=1e9;
const int MAXN=3e5+10;
vector<int>adj1[MAXN],adj2[MAXN];
vector<int>v1[MAXN],v2[MAXN];
int min1[MAXN],max1[MAXN],min2[MAXN],max2[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++)
    {
        min1[i]=INF;
        max1[i]=0;
        for(j=0;j<v1[i].size();i++)
        {
            if(min1[i]>v1[i][j])
                min1[i]=v1[i][j];
            if(max1[i]<v1[i][j])
                max1[i]=v1[i][j];
        }
    }
    for(i=0;i<N2;i++)
    {
        min2[i]=INF;
        max2[i]=0;
        for(j=0;j<v2[i].size();i++)
        {
            if(min2[i]>v2[i][j])
                min2[i]=v2[i][j];
            if(max2[i]<v2[i][j])
                max2[i]=v2[i][j];
        }
    }
    for(i=0;i<N1;i++)
    {
        for(j=0;j<N2;j++)
        {
            if(max1[i]>=min2[j]&&max2[j]>=min1[i])
            {
                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:19:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<V1.size();i++)
             ~^~~~~~~~~~
family.cpp:22: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:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v1[i].size();i++)
                 ~^~~~~~~~~~~~~
family.cpp:103:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v2[i].size();i++)
                 ~^~~~~~~~~~~~~
family.cpp:118:28: 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