백준 15563 (C++) Äventyr 1

최초 업로드: 2025-10-21 22:39:00

최근 수정 시간: 2025-10-21 22:40:16

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] Äventyr 1

[문제 링크](https://www.acmicpc.net/problem/15563)

## 문제 설명

"Äventyr bortom tidpunkten, Sista Fiolen."

여러 시간축을 이동하여 잊혀진 나라의 전설의 바이올린을 찾으려 한다. 시간축은 트리 상에서의 정점으로 표현할 수 있으며, 트리 상에서의 간선은 두 시간축 사이를 오갈 수 있음을 뜻한다. 각각의 시간축은 편의상 1부터 N까지의 자연수로 표현하자. 시간축 중 몇몇 시간축은 전설의 바이올린이 존재했던 시간축이고, 나머지는 아니다. 트리가 주어진 후, 다음과 같은 쿼리들을 Q번 수행하여라.

<ul>
	<li>1 u : u번 시간축이 바이올린이 있던 시간축이 된다.</li>
	<li>2 u : u번 시간축에서 시작하는 여행이 전설의 바이올린을 찾을 때까지 최소로 이동해야 하는 횟수를 출력한다. 방법이 없으면 -1을 출력한다.</li>
</ul>

## 입력

첫 줄에 N과 Q가 입력된다. (1 ≤ N, Q ≤ 105)

둘째 줄에 N - 1개의 시간축 A가 주어지며, 이는 i번째 시간축의 트리 상 부모가 A번째 시간축임을 뜻한다. (i = 2, 3, ..., N, 1 ≤ A ≤ N, i ≠ A)

Q개의 줄 동안 쿼리들이 c v형식으로 주어진다. c = 1이면 1번 쿼리, c = 2이면 2번 쿼리를 수행한다. 1번 쿼리는 같은 시간축에 대해 2번 이상 반복되지 않는다.

2번 노드의 부모는 1번 노드이고, 3번 노드의 부모는 2번 노드이고,...,N번 노드의 부모는 N - 1번 노드이다.

## 출력

모든 2번 쿼리의 결과를 한 줄마다 출력한다.

## 풀이
노드들이 일렬로 연결되어있기에 set에서 lower_bound로 주변 노드들이 있는지 판별할 수 있습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, q; cin >> n >> q;
 int tmp;
 for(int i=0;i<n-1;i++) cin >> tmp;

set<int> exist;
 while(q--) {
 int c, v; cin >> c >> v;
 if(c==1) {
 exist.insert(v);
 } else {
 int minDist=INT_MAX;
 auto low = exist.lower_bound(v);
 if(low!=exist.begin()) minDist = min(minDist, v-*prev(low));
 if(low!=exist.end()) minDist = min(minDist, *low-v);
 cout << (minDist==INT_MAX ? -1 : minDist) << '\n';
 }
 }
}
```