Submission #65175

#	Time	Username	Problem	Language	Result	Execution time	Memory
65175		gs18115	족보 (KOI18_family)	C++14	100 / 100	861 ms	106080 KiB

family

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=1e9;
const int MAXN=3e5+10;
vector<int>adj[2][MAXN];
bool vi[MAXN];
int K,i,j;
int root[2],N[2];
int pa[2][MAXN],leaf[2][MAXN];
int lev[MAXN],sz[MAXN],par[MAXN];
int chk[MAXN];
int cnt;
int parent(int x)
{
    if(par[x]==-1)
        return x;
    return par[x]=parent(par[x]);
}
void Union(int x,int y)
{
    int X=parent(x);
    int Y=parent(y);
    if(X==Y)
        return;
    if(lev[X]>lev[Y])
    {
        par[Y]=X;
        sz[X]+=sz[Y];
    }
    else if(lev[Y]>lev[X])
    {
        par[X]=Y;
        sz[Y]+=sz[X];
        lev[Y]++;
    }
    else if(sz[X]>sz[Y])
    {
        par[Y]=X;
        sz[X]+=sz[Y];
        lev[X]++;
    }
    else
    {
        par[X]=Y;
        sz[Y]+=sz[X];
    }
    return;
}
struct NODE
{
    int sz,lv;
    int tree,node;
}tree[2][MAXN];
vector<NODE>sorting;
bool cmp(NODE a,NODE b)
{
    return a.sz!=b.sz?a.sz<b.sz:a.lv>b.lv;
}
void pc(int t,int h)
{
    if(vi[h])
        return;
    vi[h]=true;
    if(pa[t][h]!=-1)
    {
        adj[t][pa[t][h]].push_back(h);
        pc(t,pa[t][h]);
    }
    return;
}
pair<int,int>dfs(int t,int h,int lv)
{
    tree[t][h].lv=lv;
    tree[t][h].tree=t;
    tree[t][h].node=h;
    if(adj[t][h].empty())
    {
        leaf[t][h]=h;
        tree[t][h].sz=1;
        return make_pair(h,1);
    }
    pair<int,int>P;
    P=dfs(t,adj[t][h][0],lv+1);
    leaf[t][h]=P.first;
    int s=P.second;
    for(int i=1;i<adj[t][h].size();i++)
    {
        P=dfs(t,adj[t][h][i],lv+1);
        s+=P.second;
    }
    tree[t][h].sz=s;
    return make_pair(leaf[t][h],tree[t][h].sz);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>N[0]>>N[1]>>K;
    for(i=0;i<N[0];i++)
    {
        cin>>pa[0][i];
        if(pa[0][i]==0)
            root[0]=i;
        pa[0][i]--;
    }
    for(i=0;i<N[1];i++)
    {
        cin>>pa[1][i];
        if(pa[1][i]==0)
            root[1]=i;
        pa[1][i]--;
    }
    fill(vi,vi+N[0],false);
    for(i=0;i<K;i++)
        pc(0,i);
    fill(vi,vi+N[1],false);
    for(i=0;i<K;i++)
        pc(1,i);
    dfs(0,root[0],0);
    dfs(1,root[1],0);
    for(i=0;i<2;i++)
        for(j=K;j<N[i];j++)
            sorting.push_back(tree[i][j]);
    sort(sorting.begin(),sorting.end(),cmp);
    fill(par,par+MAXN,-1);
    fill(sz,sz+MAXN,1);
    for(i=0;i<sorting.size();i++)
    {
        NODE X=sorting[i];
        for(j=0;j<adj[X.tree][X.node].size();j++)
        {
            int Y=adj[X.tree][X.node][j];
            Union(leaf[X.tree][X.node],leaf[X.tree][Y]);
        }
        if(sz[parent(leaf[X.tree][X.node])]!=X.sz)
            return cout<<"NO",0;
    }
    cout<<"YES";
    return 0;
}

Compilation message (stderr)

family.cpp: In function 'std::pair<int, int> dfs(int, int, int)':
family.cpp:88:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<adj[t][h].size();i++)
                 ~^~~~~~~~~~~~~~~~~
family.cpp: In function 'int main()':
family.cpp:130:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<sorting.size();i++)
             ~^~~~~~~~~~~~~~~
family.cpp:133:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<adj[X.tree][X.node].size();j++)
                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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