택배 운송
플래티넘 I의견: 0
2050년, 택배 최적화 연구소(KOI, Kurier Optimization Institute)는 전국 규모의 로봇 기반 택배 운송망을 구축하였다.
전국에는 \(1\)부터 \(N\)까지의 번호가 붙은 \(N\)개의 물류센터가 \(N − 1\)개의 도로로 연결되어 있다. 각 도로에는 \(1\)부터 \(N − 1\)까지의 번호가 붙어 있으며, 이 중 \(i\) (\(1 ≤ i ≤ N − 1\))번 도로는 \(U_i\)번 물류센터와 \(V_i\)번 물류센터를 두 끝점으로 하고, 길이가 \(W_i\)인 선분이다. 한 물류센터에서 다른 어떤 물류센터로도 하나 이상의 도로를 거쳐 도달할 수 있다. 즉, 택배 운송망은 물류센터가 도로를 통해 연결된 트리 구조이다. 또한, 서로 다른 두 도로는 양 끝점을 제외한 어떤 점에서도 만나지 않는다.
각 물류센터 및 각 도로 위의 임의의 점을 모두 하나의 지점이라고 하자. 물류센터와 도로의 구조가 트리이므로, 서로 다른 두 지점 사이에는 반드시 유일한 단순 경로가 존재한다. 두 지점 \(x\), \(y\) 사이의 거리 \(d(x, y)\)를 "지점 \(x\)에서 지점 \(y\)로 가는 단순 경로를 따라 이동할 때 거쳐야 하는 도로의 총 길이"로 정의하자. 단, \(x = y\)이면 \(d(x, y) = 0\)이다.
일부 물류센터에는 전파 범위가 주어진 로봇이 배치된다. 전파 범위가 \(X\)인 로봇의 초기 위치가 지점 \(p\)라면, 이 로봇은 조건 \(d(p, z) ≤ X\)를 충족하는 모든 지점
\(z\) 사이를 자유롭게 왕복하며 이동할 수 있고, 자신이 이동 가능한 범위 내의 임의의 지점에서 택배를 들어올리거나 내려놓을 수 있다.
당신은 연구소의 책임자로서, 처음에 \(1\)번 물류센터에 있는 택배를 \(N\)번 물류센터까지 운송할 수 있을지 판단하려고 한다. 로봇들은 서로 협력하여 택배를 운송할 수 있다. 즉, 한 로봇이 어느 지점에 택배를 내려놓으면 다른 로봇이 바로 그 지점에서 다시 택배를 들어올려 운송을 계속할 수 있다.
당신은 총 \(Q\)개의 시나리오에 대해, 로봇이 서로 협력하여 \(1\)번 물류센터에 있는 택배를 \(N\)번 물류센터까지 운송할 수 있을지 판단하여야 한다. \(j\) (\(1 ≤ j ≤ Q\))번째 시나리오의 형식은 다음과 같다.
- \(1\) \(A_j\) \(B_j\): \(j\)번째 시나리오는 \(j − 1\)번째 시나리오의 상황에서, 초기 위치가 \(A_j\)번 물류센터이고 전파 범위가 \(B_j\)인 로봇 하나가 추가된 상황이다.
- \(2\) \(C_j\): \(j\)번째 시나리오는 \(j − 1\)번째 시나리오의 상황에서, \(C_j\)번째 시나리오에서 새로 추가된 로봇을 제거한 상황이다. \(C_j\)번째 시나리오는 로봇을 새로 추가하는 시나리오임이 보장된다.
단, \(0\)번째 시나리오는 초기에 아무 로봇도 배치되지 않은 상황으로 간주한다.
각 시나리오에 대하여, 로봇이 서로 협력하여 \(1\)번 물류센터에 있는 택배를 \(N\)번 물류센터까지 운송할 수 있는지 판단하는 프로그램을 작성하라.
- 주어지는 모든 수는 정수이다.
- \(2 ≤ N ≤ 200\, 000\)
- \(1 ≤ Q ≤ 200\, 000\)
- \(1 ≤ i ≤ N − 1\)인 각 \(i\)에 대하여, \(1 ≤ U_i , V_i ≤ N\)이고 \(1 ≤ W_i ≤ 10^9\)
- 운송망은 연결되어 있다.
- \(1 ≤ j ≤ Q\)인 각 \(j\)에 대하여:
- \(j\)번째 시나리오가 로봇을 새로 추가하는 시나리오라면, \(1 ≤ A_j ≤ N\)이고 \(1 ≤ B_j ≤ 10^{15}\)이다.
- \(j\)번째 시나리오가 로봇을 제거하는 시나리오라면, \(1 ≤ C_j ≤ j − 1\)이고 \(C_j\)번째 시나리오는 로봇을 새로 추가하는 시나리오이다. 같은 로봇이 \(2\)회 이상 제거되지 않는다.
첫째 줄에 두 정수 \(N\), \(Q\)가 공백을 사이에 두고 주어진다.
다음 \(N − 1\)개의 줄에는 도로의 정보가 주어진다. 이 중 \(i\) (\(1 ≤ i ≤ N − 1\))번째 줄에는 세 정수 \(U_i\), \(V_i\), \(W_i\)가 공백을 사이에 두고 주어진다.
다음 \(Q\)개의 줄에는 시나리오의 정보가 주어진다. 이 중 \(j\) (\(1 ≤ j ≤ Q\))번째 줄에는 \(j\)번째 시나리오에 대한 정보가 지문에 제시된 형식대로 주어진다.
\(Q\)개의 줄을 출력한다. \(j\) (\(1 ≤ j ≤ Q\))번째 줄에는 \(j\)번째 시나리오에서 택배 운송이 가능하다면 YES를, 불가능하다면 NO를 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 8점 | \(N ≤ 100\). \(Q ≤ 6\). \(1 ≤ i ≤ N − 1\)인 각 \(i\)에 대하여, \(W_i ≤ 10\)이다. |
2 | 13점 | \(1 ≤ i ≤ N − 1\)인 각 \(i\)에 대하여, \(U_i = i\)이고 \(V_i = i + 1\)이다. 또한, \(N, Q ≤ 2\, 500\)이다. |
3 | 25점 | \(N, Q ≤ 2\, 500\) |
4 | 27점 | \(1 ≤ i ≤ N − 1\)인 각 \(i\)에 대하여, \(U_i = i\)이고 \(V_i = i + 1\)이다. |
5 | 30점 | 모든 시나리오는 로봇을 새로 추가하는 시나리오이다. |
6 | 26점 | \(1 ≤ i ≤ N − 1\)인 각 \(i\)에 대하여, \(W_i = 1\). \(1 ≤ j ≤ Q\)인 각 \(j\)에 대하여, \(j\)번째 시나리오가 로봇을 새로 추가하는 시나리오라면, \(B_j ≤ 10\)이다. |
7 | 21점 | 추가 제약 조건 없음 |
11 10
1 3 3
2 3 10
3 4 5
4 5 8
9 6 4
4 7 2
7 8 2
5 9 1
9 10 2
5 11 3
1 1 4
1 2 12
1 6 6
1 7 1
1 8 8
1 9 6
1 10 9
1 11 2
2 7
2 1NO
NO
NO
NO
NO
YES
YES
YES
YES
NO여덟 번째 시나리오를 생각하자. 총 여덟 개의 로봇이 배치되어 있다. 택배의 가능한 운송 방법 중 하나는 다음과 같다.
- 1. \(1\)번 물류센터에 있는 유일한 로봇은 전파 범위가 \(4\)이다. 이 로봇이 \(1\)번 물류센터에서 택배를 들고 \(3\)번 물류센터에 내려놓는다.
- 2. \(2\)번 물류센터에 있는 유일한 로봇은 전파 범위가 \(12\)이다. 이 로봇이 \(3\)번 물류센터로 이동해 택배를 들어올리고, \(3\)번 물류센터에서 \(4\)번 물류센터로 가는 도로에서 \(3\)번 물류센터와 \(1\)만큼 떨어진 위치에 내려놓는다.
- 3. \(8\)번 물류센터에 있는 유일한 로봇은 전파 범위가 \(8\)이다. 이 로봇이 \(3\)번 물류센터에서 \(4\)번 물류센터로 가는 도로에서 \(3\)번 물류센터와 \(1\)만큼 떨어진 위치로 이동해 택배를 들어올리고, \(4\)번 물류센터에서 \(5\)번 물류센터로 가는 도로에서 \(4\)번 물류센터와 \(3\)만큼 떨어진 위치에 내려놓는다.
- 4. \(10\)번 물류센터에 있는 유일한 로봇은 전파 범위가 \(9\)이다. 이 로봇이 \(4\)번 물류센터에서 \(5\)번 물류센터로 가는 도로에서 \(4\)번 물류센터와 \(3\)만큼 떨어진 위치로 이동해 택배를 들어올리고, \(11\)번 물류센터에 내려놓는다.
택배를 운송할 수 있으므로 YES를 출력해야 한다.
열 번째 시나리오를 생각하자. 총 여섯 개의 로봇이 배치되어 있다. 초기에
\(1\)번 물류센터에 놓여 있는 택배를 들어올릴 수 있는 로봇이 없으므로, 택배를 운송할 수 없다. 따라서 NO를 출력해야 한다.
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 1차 대회 > 고등부 3번
평가 및 의견
택배 운송
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
택배 운송