시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 1024 MB1231276.195%

문제

신이 세상을 만든 첫째 날에, 신은 지상을 만들고, 지상에 $1$에서 $N$사이의 번호를 가진 $N$ 개의 성물을 만들어 모두 서로 다른 위치에 박아넣었다. 그렇게, 지상에는 각각의 성물을 중심으로 하는 성지가 $N$ 개 생겼다.

지상은 2차원 평면으로 나타낼 수 있고, $i$번 성물은 좌표 $(X_i,Y_i)$에 박혀있다. 어떤 좌표 $(x,y)$가 $i$번 성물을 중심으로 하는 성지에 포함될 조건은, $L_i(x,y)=\sqrt{(X_i-x)^2+(Y_i-y)^2}$라고 할 때, $L_i(x,y)$가 $L_1(x,y), L_2(x,y), \cdots, L_N(x,y)$중 최솟값이 되는 것이다. 이런 상황에서, 두 성지는 같은 좌표들을 공유할 수 있고, 이때 두 성지의 중심이 되는 두 성물 사이에는 연결이 생긴다. 두 성지가 공유하는 점들의 형태는 선분, 반직선, 혹은 직선이 되는데, 신은 선분이 생기면 길이가 모두 $10^{-6}$이상이 되도록 성물을 배치했다.

어떤 두 성물이 연결되느냐에 따라, 연결의 세기는 서로 다르다. $i$번 성물에는 $S_i$라는 이름이 붙어 있어, $i$번 성물과 $j$번 성물이 연결되면, 두 성물의 이름이 비슷한 정도 만큼 연결이 강해진다. $S_i$와 $S_j$가 비슷한 정도 $C(i,j)$가 $l$라는 것은, $S_i$에서 길이가 $l$인 연속한 일부분 중 하나가 $S_j$에서 연속하게 등장하면서, 길이가 $l+1$인 연속한 일부분은 하나도 $S_j$에 연속하게 등장하지 않는다는 뜻이다. 만약, $S_i$와 $S_j$에 같은 문자가 하나도 없다면, $C(i,j)=0$이다. $i$번 성물과 $j$번 성물 사이에 연결이 있다면 결국 $C(i,j)$의 크기가 연결의 세기가 된다.

신이 세상을 만든 둘째 날에, 신은 천상을 만들고, 천상에 $1$에서 $N$사이의 번호를 가진 $N$ 개의 을 만들어 박아넣었다. 이 $N$ 개의 별은 지상에 있는 $N$ 개의 성물을 본떠 만들어졌고, 또한 이들의 연결 중 $N-1$ 개를 본떠 별의 연결이 만들어졌다. 별이 만들어진 결과, 하나의 성물이 하나의 별에 대응되었기에, $i$번 성물과 대응된 별의 번호는 유일하게 $b_i$가 된다.

신은 가장 처음 $1$번 성물을 본떠 $1$번 별을 만들었다. 즉, $b_1=1$이다. 그리고 번호 순서대로 나머지 별들을 만들었다. $u(\ge 2)$번 별을 만들 때는, 이미 본떠 별을 만든 $u-1$ 개의 성물 중 하나와, 아직 본뜨지 않은 $N-u+1$ 개의 성물 중 하나 간의 연결 중에서 가장 연결이 강한 연결을, 그것이 여럿이면 이미 성물을 본뜬 별의 번호가 가장 큰 연결을, 그것도 여럿이면 아직 본뜨지 않은 성물의 번호가 가장 작은 연결을 골랐다. 이 연결이 이미 본떠진 $i$번 성물과 아직 본떠지지 않은 $j$번 성물을 연결하고 있다면, $j$번 성물을 본떠 $u$번 별을 만들게 되어 $b_j=u$가 된다. $b_i$가 먼저 만들어진 별이기 때문에, $b_i$는 $b_j$의 부모 별이라고 칭한다.

신이 세상을 만든 셋째 날에, 신은 지상에 순례자들을 만들었다.

태초가 지난 후 시간이 많이 흐른 지금, 많은 순례자들이 지상을 순례하고 있다. 하지만 특별히, 어떤 순례자들은 신께 허락을 구해, 천상의 길을 통한 순례를 진행하기도 한다. 만약 어떤 순례자가 지상의 좌표 $(x_s,y_s)$에서 지상의 좌표 $(x_e,y_e)$까지 천상의 길을 통해 이동하는 순례를 계획하고 있다고 하자. $(x_s,y_s)$가 $i$번 성지에 속하고, $(x_e,y_e)$가 $j$번 성지에 속한다면, 순례자는 $i$번 성지에서 육체에서 벗어난 정신체가 되어 $b_i$번 별로 이동하고, 존재하는 별의 연결을 따라 $b_j$번 별로 이동한 다음, $j$번 성지의 좌표 $(x_e,y_e)$로 이동하여 다시 육체를 얻는 것으로 순례를 마칠 수 있다.

이렇게 순례를 마치면, 순례자에게 육체적인 피로는 없지만, 두 별 사이를 이동한 거리 중 가장 멀었던 거리 만큼 정신적인 피로를 느끼게 된다. 두 별 $b_i$와 $b_j$사이의 거리는 그 둘을 본뜬 성물의 영향을 받아 $C(i,j)\cdot[(X_i-X_j)^2+(Y_i-Y_j)^2]$이다. 순례자는 당연히, 정신적 피로가 최소화되도록 순례를 진행한다.

순례자들이 천상의 길을 통해 순례를 하는 동안, 별들도 이동하여 천상의 길은 계속해서 변화한다. 정확히는, 어떤 별과 부모 별 사이의 연결이 사라지고 새로운 부모 별과의 연결이 생긴다.

태초에 천상의 길이 어떻게 구성되었는지 구하여라. 그리고 태초가 지난 후 천상의 길을 이용하는 순례자들의 순례 계획과 천상의 길의 변화가 주어질 때, 순례자들이 느끼게 될 정신적 피로가 어떻게 되는지 구하여라.

입력

첫 번째 줄에, 별의 개수를 나타내는 자연수 $N$, 순례 계획의 개수 $Q_1$, 천상의 길이 변화하는 횟수 $Q_2$가 주어진다.

다음 $N$ 개의 줄의 $i$번째 줄에, $i$번 성물의 좌표를 나타내는 두 정수 $X_i$, $Y_i$($-10^6 \leq X_i, Y_i \leq 10^6$)와, 성물의 이름을 의미하는 알파벳 소문자로 구성된 문자열 $S_i$가 주어진다. 같은 좌표에 서로 다른 두 성물이 위치하지 않는다.

다음 $Q_1+Q_2$ 개의 줄의 각 줄에 질의가 다음 형식 중 하나로 주어진다.

1 $x_s$ $y_s$ $x_e$ $y_e$ : 순례자가 지상의 좌표 $(x_s,y_s)$에서 지상의 좌표 $(x_e,y_e)$로 천상의 길을 통한 순례를 계획한다. 이 순례를 진행할 때, 정신적인 피로의 최솟값을 출력해야 한다. $-10^6 \leq x_s, y_s, x_e, y_e \leq 10^6$를 모두 만족하는 입력이 주어지며, $(x_s,y_s)$와의 유클리드 거리가 $10^{-6}$ 이하인 점은 모두 하나의 성지에 속함이 보장된다. 이는 $(x_e,y_e)$도 마찬가지다.

2 $u$ $p$ : $u$번 별의 부모별이 $p$로 바뀐다. $1 \leq p < u \leq N$을 만족하는 입력이 주어진다.
 

출력

먼저 $N-1$ 개의 줄에 걸쳐 태초에 천상의 길이 어떻게 구성되었는지 출력한다. 이 중 $i$번째 줄에는 $i+1$번 별과 대응된 성물의 번호 $a_{i+1}$, 태초에 $i+1$번 별의 부모 별이었던 별의 번호 $p_{i+1}$, $a_{i+1}$번 성물과 $p_{i+1}$번 별에 대응 된 두 성물을 연결하는 연결의 세기를 출력해야 한다.

그리고 다음 $Q_1$ 개의 줄에 걸쳐, 순례 계획과 천상의 길의 변화가 주어진 순서대로 순례를 진행하면 순례자가 느끼게 될 정신적 피로의 최솟값을 한 줄에 하나씩 출력한다.

서브태스크 1 (1점)

  • $3 \le N, Q_1, Q_2 \le 8$
  • $1 \le |S_i|, \sum |S_i| \le 20$

서브태스크 2 (10점)

  • $3 \le N, Q_1, Q_2 \le 888$
  • $1 \le |S_i|, \sum |S_i| \le 2\ 020$

서브태스크 3 (100점)

  • $3 \le N, Q_1, Q_2 \le 88\ 888$
  • $1 \le |S_i|, \sum |S_i| \le 202\ 020$

예제 입력 1

9 10 5
1 0 aabb
1 9 abab
3 3 aaab
3 7 abbb
5 5 baab
7 3 bbaa
7 7 abba
10 1 bbbb
9 10 aaaa
1 0 0 10 10
1 7 10 5 6
1 5 12 12 5
2 5 1
1 3 6 2 3
1 0 8 8 0
1 1 2 7 4
2 9 4
2 9 4
2 9 4
1 5 6 7 8
1 8 3 10 9
2 7 2
1 5 4 6 5
1 4 5 3 10

예제 출력 1

3 1 3
5 2 3
6 3 3
7 4 3
4 5 3
2 6 2
8 5 2
9 7 1
65
65
90
255
90
39
255
106
0
80

 


 

출처

Contest > BOJ User Contest > 전시관 > 제1 전시관 8번

  • 문제를 만든 사람: zigui

채점 및 기타 정보

  • 예제는 채점하지 않는다.