| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 | 1024 MB | 204 | 12 | 11 | 8.527% |
서울과학고는 $N$개의 방과 서로 다른 두 방을 연결하는 $N-1$개의 복도로 이루어진 트리 형태로 표현할 수 있다. 모든 복도는 양방향으로 이동할 수 있고, 복도를 이용해 모든 방 사이를 이동할 수 있다. 하나의 복도를 통과하는 데 걸리는 시간은 1ドル$이다.
브루는 졸업을 앞두고 서울과학고에서 함께 추억을 쌓았던 $K$명의 친구들과 사진을 찍으려고 한다.
브루는 $K$명의 친구들 각각과 함께 두 장의 커플 사진을 찍을 것이다. 이때 $i$번 친구와는 각각 $A_i$번 방과 $B_i$번 방에서 사진을 찍을 것이다. 1ドル$번 방에서 $B_i$번 방까지 이동하기 위해 반드시 $A_i$번 방을 지나야 함이 보장된다.
총 2ドルK$장의 사진을 찍으려면 학교 내에서 이동해야 하지만, 모든 친구와 함께 이동하게 되면 혼잡해진다. 따라서 브루와 친구들은 다음과 같은 방식으로 이동하기로 했다.
먼저 브루는 서울과학고를 순회하는 계획을 세운다. 순회 계획은 다음 조건에 맞아야 한다.
편의상 순회 계획을 수열 $S_0,S_1,\cdots ,S_{2N-2}$로 나타내자. 이때 $S_i$는 시간 $i$에 브루가 막 도착한 방의 번호이다.
다음으로, $K$명의 친구들은 브루의 순회에 함께할 시간을 정한다. $i$번째 친구는 자신이 브루의 순회에 합류할 시각 $L_i$와 순회에서 빠져나올 시각 $R_i$를 정한다. 이때, $i$번 친구는 $A_i$번 방과 $B_i$번 방에서 브루와 함께 사진을 찍어야 하므로, 이 시간 간격 동안 브루가 $A_i$번 방과 $B_i$번 방을 모두 방문해야 한다. 즉, $L_i\le e,f\le R_i;$ $S_e=A_i;$ $S_f=B_i$인 정수 $e$와 $f$가 존재해야 한다.
$i$번 친구의 이동 시간은 $R_i-L_i$로 정의된다. 브루는 모든 친구의 이동 시간 합을 최소화하고자 한다. 브루를 위해 가능한 최소 이동 시간 합을 구해 주자.
첫째 줄에 방의 수 $N$과 친구의 수 $K$가 주어진다.
둘째 줄부터 $N$번째 줄까지 $i+1$번째 줄에는 $i$번 복도가 연결하는 두 방의 번호 $U_i$와 $V_i$가 공백으로 구분되어 주어진다.
$N+1$번째 줄부터 $N+K$번째 줄까지 $N+i$번째 줄에는 $i$번 친구와 같이 사진을 찍을 방의 번호 $A_i$와 $B_i$가 공백으로 구분되어 주어진다.
모든 친구의 이동 시간 합으로 가능한 최솟값을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | $N \le 10,ドル $K \le 10$ |
| 2 | 25 | $N \le 100,ドル 1ドル$번 방과 연결된 복도는 2개 이하이고, 나머지 방과 연결된 복도는 각각 3개 이하이다. |
| 3 | 47 | $N \le 100$ |
| 4 | 16 | 추가 제한 조건이 없다. |
7 3 1 2 1 3 2 4 2 5 3 6 3 7 1 4 2 5 1 7
5
School > 서울과학고등학교 > SciOI 2023 B-2번