티스토리 뷰

IOI/IOI2020

IOI2020 Day2 stations 풀이

전명우 2020. 9. 23. 18:16

문제 및 채점: 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로 가야 한다. 이와 같이 정점에 번호를 적을 경우, 가려고 하는 정점에 적힌 번호와 인접한 정점에 적힌 번호를 기반으로 간단하게 주어지는 질문을 해결할 수 있다.

 

더보기

'IOI > IOI2020' 카테고리의 다른 글

IOI2020 Day2 mushrooms 풀이  (0) 2020.09.24
IOI2020 Day2 biscuits 풀이  (0) 2020.09.23
IOI2020 Day2 stations 풀이  (0) 2020.09.23
IOI2020 Day1 plants 풀이  (0) 2020.09.22
IOI2020 Day1 tickets 풀이  (0) 2020.09.22
IOI2020 Day1 supertrees 풀이  (0) 2020.09.22
댓글
댓글쓰기 폼