<div id="readability-page-1" class="page"><div>문제 및 채점: <a href="https://oj.uz/problem/view/IOI20_stations" target="_blank" rel="noopener">oj.uz</a>

$N$ 개의 정점으로 이루어진 트리가 주어진다. 각 정점에 $0$ 이상 $K$ 이하의 수를 서로 다르게 적는다. 수 $i$가 적힌 정점을 정점 $i$라고 하자. 정점 $s$에 인접한 정점에 적힌 수들이 배열 $c$로 주어질 때, 정점 $s$에서 정점 $t$로 가기 위해 어느 인접한 정점으로 이동하면 되는지 구하는 질문이 주어진다. 문제는 정점에 수를 적는 함수와, 주어지는 질문을 해결하는 함수 두 개를 작성하는 것이다. 단, 정점에 적는 수 이외에 전역 변수와 같이 외부 메모리를 참조하여 질문을 해결할 수 없다.

서브태스크 1, 2, 3, 4
이 서브태스크에 대한 풀이는 따로 서술하지 않겠다. 서브태스크 1, 2, 3은 주어지는 트리의 모양이 일자, 완전 이진 트리 등 정해진 모양을 가지며, 그 모양에 따라 수를 적절히 적어주어 주어지는 질문을 해결할 수 있다.

서브태스크 5
임의의 정점을 루트로 정해 루트가 있는 트리로 만든다. 루트부터 시작하여 dfs 순서로 정점을 탐색하며 1부터 $N$까지의 수를 적는데 정점 깊이의 홀짝성에 따라 수를 preorder, postorder로 적는다.
<figure data-origin-width="366" data-origin-height="272" data-filename="stations.png" data-ke-mobilestyle="widthContent"><img src="https://blog.kakaocdn.net/dn/7QQhN/btqJjvw4h6t/NWanqbbsYYbfxYlyLry4Fk/img.png" data-origin-width="366" data-origin-height="272" data-filename="stations.png" data-ke-mobilestyle="widthContent"></figure>
위 그림은 트리에서 언급한 방식으로 정점에 수를 적은 예시이다. 정점 11에서 시작하여, 10 이상 11 미만의 번호가 적힌 정점으로 가기 위해서는 정점 10으로 가야 하고, 6 이상 10 미만의 번호가 적힌 정점으로 가기 위해서는 정점 6으로 가야 하고, 5 이상 6 미만의 번호가 적힌 정점으로 가기 위해서는 정점 5로 가야 하고, 1이상 5 미만의 번호가 적힌 정점으로 가기 위해서는 정점 1로 가야 한다. 정점 1에서 시작하여, 1 초과 4 이하의 번호가 적힌 정점으로 가기 위해서는 정점 4로 가야 하고, 4 초과 11 미만의 번호가 적힌 정점으로 가기 위해서는 정점 11로 가야 한다. 이와 같이 정점에 번호를 적을 경우, 가려고 하는 정점에 적힌 번호와 인접한 정점에 적힌 번호를 기반으로 간단하게 주어지는 질문을 해결할 수 있다.

</div></div>

PS 이야기

문제 및 채점: oj.uz
 
$N$ 개의 정점으로 이루어진 트리가 주어진다. 각 정점에 $0$ 이상 $K$ 이하의 수를 서로 다르게 적는다. 수 $i$가 적힌 정점을 정점 $i$라고 하자. 정점 $s$에 인접한 정점에 적힌 수들이 배열 $c$로 주어질 때, 정점 $s$에서 정점 $t$로 가기 위해 어느 인접한 정점으로 이동하면 되는지 구하는 질문이 주어진다. 문제는 정점에 수를 적는 함수와, 주어지는 질문을 해결하는 함수 두 개를 작성하는 것이다. 단, 정점에 적는 수 이외에 전역 변수와 같이 외부 메모리를 참조하여 질문을 해결할 수 없다.
 
서브태스크 1, 2, 3, 4
이 서브태스크에 대한 풀이는 따로 서술하지 않겠다. 서브태스크 1, 2, 3은 주어지는 트리의 모양이 일자, 완전 이진 트리 등 정해진 모양을 가지며, 그 모양에 따라 수를 적절히 적어주어 주어지는 질문을 해결할 수 있다.
 
서브태스크 5
임의의 정점을 루트로 정해 루트가 있는 트리로 만든다. 루트부터 시작하여 dfs 순서로 정점을 탐색하며 1부터 $N$까지의 수를 적는데 정점 깊이의 홀짝성에 따라 수를 preorder, postorder로 적는다.
위 그림은 트리에서 언급한 방식으로 정점에 수를 적은 예시이다. 정점 11에서 시작하여, 10 이상 11 미만의 번호가 적힌 정점으로 가기 위해서는 정점 10으로 가야 하고, 6 이상 10 미만의 번호가 적힌 정점으로 가기 위해서는 정점 6으로 가야 하고, 5 이상 6 미만의 번호가 적힌 정점으로 가기 위해서는 정점 5로 가야 하고, 1이상 5 미만의 번호가 적힌 정점으로 가기 위해서는 정점 1로 가야 한다. 정점 1에서 시작하여, 1 초과 4 이하의 번호가 적힌 정점으로 가기 위해서는 정점 4로 가야 하고, 4 초과 11 미만의 번호가 적힌 정점으로 가기 위해서는 정점 11로 가야 한다. 이와 같이 정점에 번호를 적을 경우, 가려고 하는 정점에 적힌 번호와 인접한 정점에 적힌 번호를 기반으로 간단하게 주어지는 질문을 해결할 수 있다.
 
더보기
#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
vector<int> label(int N, int K, vector<int> u, vector<int> v)
{
	vector<vector<int>> con(N);
	for (int i=0;i<N-1;i++)
		con[u[i]].push_back(v[i]),
		con[v[i]].push_back(u[i]);
	vector<int> labels(N); int idx = 0;
	function<void(int, int)> dfs;
	dfs = [&](int n, int p){
		if (p == -1 || !labels[p]) labels[n] = ++idx;
		for (int t: con[n]) if (t != p)
			dfs(t, n);
		if (!labels[n]) labels[n] = ++idx;
	};
	dfs(0, -1);
	return labels;
}
int find_next_station(int s, int t, vector<int> c)
{
	if (c.back() < s) reverse(c.begin(), c.end());
	for (int x: c) if (min(s, x) <= t && t <= max(s, x)) return x;
	return c.back();
}

IOI2020 Day2 stations 풀이

댓글