Submission #333504

#	Time	Username	Problem	Language	Result	Execution time	Memory
333504		leinad2	족보 (KOI18_family)	C++17	100 / 100	437 ms	50028 KiB

family

#include<bits/stdc++.h>
using namespace std;
int k, par[300010], i, j, a, s[300010];
vector<pair<int, int> >v;
struct tree
{
    int n, leaf[300010], sz[300010];
    vector<int>adj[300010];
    void dfs(int v)
    {
        if(v&&v<=k)
        {
            sz[v]=1;
            leaf[v]=v;
            return;
        }
        for(int x=0;x<adj[v].size();x++)
        {
            dfs(adj[v][x]);
            leaf[v]=leaf[adj[v][x]];
            sz[v]+=sz[adj[v][x]];
        }
    }
}t1, t2;
int Find(int x)
{
    if(x==par[x])return x;
    return par[x]=Find(par[x]);
}
void Union(int a, int b)
{
    a=Find(a);
    b=Find(b);
    if(a!=b)
    {
        s[a]+=s[b];
        s[b]=0;
        par[b]=a;
    }
}
int main()
{
    scanf("%d %d %d", &t1.n, &t2.n, &k);
    for(i=0;i++<k;)par[i]=i,s[i]=1;
    for(i=0;i++<t1.n;)
    {
        scanf("%d", &a);
        t1.adj[a].push_back(i);
    }
    for(i=0;i++<t2.n;)
    {
        scanf("%d", &a);
        t2.adj[a].push_back(i);
    }
    t1.dfs(0);
    t2.dfs(0);
    for(i=0;i++<t1.n;)
    {
        if(t1.adj[i].size()>1)v.push_back({t1.sz[i], i});
    }
    for(i=0;i++<t2.n;)
    {
        if(t2.adj[i].size()>1)v.push_back({t2.sz[i], i+t1.n});
    }
    sort(v.begin(), v.end());
    for(pair<int, int>i:v)
    {
        if(i.second>t1.n)
        {
            i.second-=t1.n;
            a=t2.leaf[i.second];
            for(int j:t2.adj[i.second])
            {
                Union(t2.leaf[j], a);
            }
        }
        else
        {
            a=t1.leaf[i.second];
            for(int j:t1.adj[i.second])
            {
                Union(t1.leaf[j], a);
            }
        }
        if(s[Find(a)]!=i.first)
        {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
}

Compilation message (stderr)

family.cpp: In member function 'void tree::dfs(int)':
family.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for(int x=0;x<adj[v].size();x++)
      |                     ~^~~~~~~~~~~~~~
family.cpp: In function 'int main()':
family.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |     scanf("%d %d %d", &t1.n, &t2.n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
family.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~
family.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~

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