Submission #333494

#	Time	Username	Problem	Language	Result	Execution time	Memory
333494		leinad2	족보 (KOI18_family)	C++17	0 / 100	10 ms	14444 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.sz[i]>1)v.push_back({t1.sz[i], i});
    }
    for(i=0;i++<t2.n;)
    {
        if(t2.sz[i]>1)v.push_back({t2.sz[i], i+t1.n});
    }
    sort(v.begin(), v.end());
    for(i=0;i<v.size();i++)
    {
        if(v[i].second>t1.n)
        {
            v[i].second-=t1.n;
            for(j=0;j+1<t2.adj[v[i].second].size();j++)
            {
                Union(t2.leaf[t2.adj[v[i].second][j]], t2.leaf[t2.adj[v[i].second].back()]);
            }
            if(s[Find(t2.leaf[t2.adj[v[i].second].back()])]!=t2.sz[v[i].second])
            {
                puts("NO");
                return 0;
            }
        }
        else
        {
            for(j=0;j+1<t1.adj[v[i].second].size();j++)
            {
                Union(t1.leaf[t1.adj[v[i].second][j]], t1.leaf[t1.adj[v[i].second].back()]);
            }
            if(s[Find(t1.leaf[t1.adj[v[i].second].back()])]!=t1.sz[v[i].second])
            {
                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:66:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(i=0;i<v.size();i++)
      |             ~^~~~~~~~~
family.cpp:71:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for(j=0;j+1<t2.adj[v[i].second].size();j++)
      |                     ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
family.cpp:83:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for(j=0;j+1<t1.adj[v[i].second].size();j++)
      |                     ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
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: 0 / 17
• Subtask 2: 0 / 27
• Subtask 3: 0 / 15
• Subtask 4: 0 / 41