oj.uz

답안 #64801

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
64801 2018-08-05T17:12:23 Z kjp4155 족보 (KOI18_family) C++17
0 / 100
 19 ms 14568 KB 
#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, node;
	// Smaller event first. Deeper event first. 
	bool operator < (event e){
		return len < e.len;
	}
};

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], 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

family.cpp: In function 'int main()':
family.cpp:60: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:70: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
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 14456 KB Output is correct
2 Incorrect 16 ms 14568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 14456 KB Output is correct
2 Incorrect 16 ms 14568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 14456 KB Output is correct
2 Incorrect 16 ms 14568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 14456 KB Output is correct
2 Incorrect 16 ms 14568 KB Output isn't correct
3 Halted 0 ms 0 KB -