페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2501

[고등부] 2025 KOI 1차대회 대비 모의고사 (4주차)

네트워크 정비
서브태스크
2초 1024MB

문제

정올 왕국은 평면 좌표 위에 존재한다.
N개의 마을이 있고, 각 마을에는 1번부터 N번까지 번호가 붙어 있다.
마을 i는 좌표 (i, 0)에 있는 점으로 간주한다.

지금 정올 왕국에서는 이 마을들을 연결하는 통신 회선을 정비하려 한다.
장애에 대비하여 통신 회선은 두 개의 네트워크로 나눠 관리하고 있다.

아래 그림은 문제의 두 예제에 대한 그림이다.
회색 원은 네트워크 1의 허브, 검은색 원은 네트워크 2의 허브, 흰색 원은 마을을 나타낸다.

  • 네트워크 k에는 허브가 M_k로 이루어져 있고, 마을과 허브 혹은 허브와 허브를 잇는 회선이 총 N + M_k – 1개 있다.

  • 네트워크 k의 허브 j (1≤j≤M_k)는 좌표 (X_{k,j}, Y_{k,j})에 위치한다.

  • 각 회선은 두 끝점을 잇는 선분으로 간주하며, 서로 끝점 이외의 교차점이 없도록 배치되어 있다.

  • 네트워크 1의 모든 허브는 y>0에, 네트워크 2의 모든 허브는 y<0에 놓여 있다.

두 지점이 통신 가능하다는 것은, 회선을 따라 이동하며 한 지점에서 다른 지점으로 갈 수 있음을 의미한다.
문제에서 주어진 조건 하에, 네트워크 1만으로도 임의의 두 마을 및 허브가 모두 통신 가능하며, 네트워크 2만으로도 마찬가지이다.

이 계획에 대한 안전성을 평가하기 위해, 두 정수 A (A ≥ 0), B (B ≤ 0)를 받아서
y좌표가 A보다 큰 모든 허브와 y좌표가 B보다 작은 모든 허브를 ‘파괴’한다고 가정하자.

허브가 파괴되면 그 허브를 경유하는 통신이 모두 불가능해진다.

마을 및 두 계통의 정보가 주어지고, Q개의 쿼리가 주어진다.
각 쿼리 i에는 정수 A_i가 주어졌을 때, "y > A_i인 모든 허브와 y < B인 모든 허브를 파괴해도
모든 마을 사이의 통신이 유지되는” 가장 큰 정수 B_i (B_i ≤ 0)를 구하여라.


입력

첫 번째 줄에는 네 개의 정수 N, M_1, M_2 , Q가 공백으로 구분되어 주어진다.

이어 M_1 + (N + M_1 - 1) 줄에 네트워크 1의 정보가 주어진다.

  • 첫 번째 M_1줄의 i번째 줄엔 두 정수 X_{1i}, Y_{1i}가 주어진다.

  • 이어 N+M_1-1줄의 i번째 줄엔 회선 i의 정보를 나타내는 세 정수 T_{1i}, C_{1,i}, D_{1,i}가 주어진다.

    • T_{1i}=1인 경우, 마을 C_{1i}와 허브 D_{1i}를 잇는다. (1≤C_{1i}≤N, 1≤D_{1i}≤M_1 )

    • T_{1i}=2인 경우, 허브 C_{1i}와 허브 D_{1i}를 잇는다. (1≤C_{1i},D_{1i}≤M_i, C_{1i} \ne D_{1i})

이어 M_2 + (N + M_2 - 1) 줄에 네트워크 2의 정보가 주어진다.

  • 첫 번째 M_2줄의 i번째 줄엔 두 정수 X_{2i}, Y_{2i}가 주어진다.

  • 이어 N+M_2-1줄의 i번째 줄엔 회선 i의 정보를 나타내는 세 정수 T_{2i}, C_{2,i}, D_{2,i}가 주어진다.

    • T_{2i}=1인 경우, 마을 C_{2i}와 허브 D_{2i}를 잇는다. (1≤C_{2i}≤N, 1≤D_{2i}≤M_2)

    • T_{2i}=2인 경우, 허브 C_{2i}와 허브 D_{2i}를 잇는다. (1≤C_{2i},D_{2i}≤M_i, C_{2i} \ne D_{2i})

다음 Q 줄의 i번째 줄에는 정수 A_i가 주어진다.

[제약 사항]

  • 1≤N, M_1, M_2≤100 000

  • −10^9 ≤ X_{1i}≤ 10^9 (1≤i≤M_1)

  • −10^9 ≤ X_{2i}≤ 10^9 (1≤i≤M_2)

  • 1 ≤ Y_{1i }≤ 10^9

  • -10^9 ≤ Y_{2i }≤ -1

  • 허브 좌표들은 서로 겹치지 않는다.

  • 1≤Q≤100 000

  • 0≤A_i≤10^9 (1≤i≤Q)

  • 임의의 두 회선은 끝점 이외에서 교차하지 않는다.

  • 첫 번째 네트워크만으로도, 두 번째 네트워크만으로도 각각 모든 마을과 허브가 통신 가능하다.


출력

Q줄에 걸쳐, i번째 줄에 질문 i의 답 B_i를 출력하라.
단, B_i=0인 경우 정답은 "0"으로, "−0"은 허용되지 않는다.


부분문제

번호 점수 조건
#125점

N, M_1, M_2, Q ≤ 100

#225점

N, M_1, M_2, Q ≤ 1 000

#325점

N, M_1, M_2, Q ≤ 30 000

#425점

추가 제약 없음


예제 #1

4 3 3 1
1 1
3 2
2 3
1 1 1
1 2 1
1 3 2
1 4 2
2 1 3
2 2 3
3 -1
2 -2
1 -3
1 1 3
1 2 2
1 3 1
1 4 1
2 1 2
2 2 3
2
-2

예제 #2

6 4 5 4
2 1
4 1
3 3
5 2
1 1 1
1 2 1
1 3 2
1 4 2
2 2 4
1 5 4
1 6 4
2 1 3
2 4 3
3 -3
5 -1
2 -2
2 -1
4 -2
1 2 4
1 3 4
1 1 4
2 1 3
1 5 2
1 6 2
1 4 5
2 2 5
1 3 1
2 5 1
3
1
2
0
0
-2
-1
-3
로그인해야 코드를 작성할 수 있어요.