| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 64801 |
2018-08-05T17:12:23 Z |
kjp4155 |
None (KOI18_family) |
C++17 |
|
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);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
