Submission #474495

#	Time	Username	Problem	Language	Result	Execution time	Memory
474495		jamielim	족보 (KOI18_family)	C++14	100 / 100	601 ms	73504 KiB

family

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n[2],k;
vector<int> adj[2][300005];
int arr[2][300005];
int par[2][300005];
vector<pair<int,ii> > sorted;

void dfs(int x,int tree){
	if(x!=0&&x<=k){
		arr[tree][x]=1;
		par[tree][x]=x;
	}
	if(SZ(adj[tree][x])>0){
		for(int i=0;i<SZ(adj[tree][x]);i++){
			int y=adj[tree][x][i];
			dfs(y,tree);
			arr[tree][x]+=arr[tree][y];
			par[tree][x]=par[tree][y];
		}
		sorted.pb(arr[tree][x],mp(tree,x));
	}
}

int p[300005],sz[300005];
int root(int x){return p[x]=(p[x]==x?x:root(p[x]));}

int main(){
	scanf("%d%d%d",&n[0],&n[1],&k);
	int pa;
	for(int a=0;a<2;a++){
		for(int i=1;i<=n[a];i++){
			scanf("%d",&pa);
			adj[a][pa].pb(i);
		}
	}
	dfs(0,0);
	dfs(0,1);
	sort(ALL(sorted));
	for(int i=1;i<=k;i++){p[i]=i;sz[i]=1;}
	for(pair<int,ii> i:sorted){
		for(int j:adj[i.se.fi][i.se.se]){
			int ra=root(par[i.se.fi][i.se.se]),rb=root(par[i.se.fi][j]);
			if(ra==rb)continue;
			p[ra]=rb;
			sz[rb]+=sz[ra];
		}
		if(SZ(adj[i.se.fi][i.se.se])<=1)continue;
		if(sz[root(par[i.se.fi][i.se.se])]!=i.fi){
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
}

Compilation message (stderr)

family.cpp: In function 'int main()':
family.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d%d%d",&n[0],&n[1],&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
family.cpp:49:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |    scanf("%d",&pa);
      |    ~~~~~^~~~~~~~~~

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