Submission #64803

#	Time	Username	Problem	Language	Result	Execution time	Memory
64803		kjp4155	족보 (KOI18_family)	C++17	100 / 100	1093 ms	65352 KiB

family

#include <stdio.h>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int,int> Pi;

/* Union Find 자료구조 */
int pa[300500], cnt[300500]; 
int find(int x){
	if( pa[x] == x ) return x;
	return pa[x] = find(pa[x]);
}
void uni(int a, int b){
	a = find(a); b = find(b);
	if( a == b ) return;
	pa[a] = b;
	cnt[b] += cnt[a];
}

struct event{
	int t, len, level, node;
	// Smaller event first. Deeper event first. 
	bool operator < (event e){
		if( len != e.len ) return len < e.len;
		return level > e.level;
	}
};

int N[2],K;
vector<int> E[2][300500];
int root[2];
int sz[2][300500], leaf[2][300500], level[2][300500];
int timer = 0;


// dfs를 돌면서 각 내부정점의 부트리에 속하는 아무 리프노드 하나와 총 리프개수를 저장
// 또한, 각 정점의 깊이도 같이 저장
// dfs함수의 리턴값은 (아무 리프노드, 리프노드 개수) 이다.
Pi dfs(int t, int x, int l){
	level[t][x] = l;

	if( 1 <= x && x <= K ){
		timer++;
		leaf[t][x] = x;
		sz[t][x] = 1;
		return {x,1};
	}
	
	for(auto e : E[t][x]){
		Pi res = dfs(t, e, l+1);
		leaf[t][x] = res.first;
		sz[t][x] += res.second; 
	}
	
	return {leaf[t][x], sz[t][x]};
}

int main(){
	scanf("%d%d%d",&N[0],&N[1],&K);

	// Union Find 초기화
	for(int i=1;i<=K;i++){
		pa[i] = i; cnt[i] = 1;
	}

	// 트리 그래프 만들기
	for(int t=0;t<2;t++){
		for(int i=1;i<=N[t];i++){
			int x; scanf("%d",&x);
			if( x == 0 ) root[t] = i;
			else E[t][x].push_back(i);
		}
	}

	// dfs를 돌면서 각 내부정점의 부트리에 속하는 아무 리프노드 하나와 총 리프개수를 저장
	// 또한, 각 정점의 깊이도 같이 저장
	dfs( 0, root[0] , 0);
	timer = 0;
	dfs( 1, root[1] , 0);

	// 모든 내부정점에 대해 event 만들어 주기
	vector<event> events;
	for(int t=0;t<2;t++){
		for(int i=K+1;i<=N[t];i++){
			events.push_back({t, sz[t][i], level[t][i], i});
		}
	}

	// event들을 (길이,level)순으로 정렬
	sort(events.begin(), events.end());

	// 각 event를 정렬된 순서대로 보면서, 현재 정점의 부 트리에 속한 모든 리프노드를
	// Union 해준다. 이후 현재 정점의 부 트리에 속한 리프노트 개수와 union된 집합의 크기를 비교한다.
	for(auto e : events){
		for(auto x : E[e.t][e.node]){
			uni(leaf[e.t][e.node], leaf[e.t][x]);
		}
		if( cnt[find(leaf[e.t][e.node])] != e.len ){
			printf("NO\n");
			return 0;
		}
	}

	printf("YES\n");
}

Compilation message (stderr)

family.cpp: In function 'int main()':
family.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&N[0],&N[1],&K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
family.cpp:71:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d",&x);
           ~~~~~^~~~~~~~~

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