Informatica Online Judge

  낚시꾼 민제 #2 [2444 / 098C]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 5   Total Tried : 13


The Champion of this Problem (C++) : gs17003 - ms / 1869byte
My Best Submission (C++) : N/A

[35th 이강민(gs17074)]
Writer ID : [gs17074]

Background

민제는 몽골에서 고기를 낚고 싶어 했던 미래의 낚시꾼 유망주였다. 하지만 몽골은 내륙에 위치해있기 때문에 꿈을 이룰 수 없었다.
그런데 어느 날, 이런 상황을 보고 불쌍해 하던 순천의 왕 세빈이가 민제가 낚시를 할 수 있도록 앞바다를 주기로 했다.
앞바다에는 N개의 섬이 있다. i번째 섬에는 현재 a_i 마리의 물고기가 있고, 민제는 배가 없기 때문에 각 섬에서 다리로 연결된 곳끼리만 이동할 수 있다.
맨 처음 앞바다에는 다리가 한 개도 없기 때문에 N개의 섬이 모두 분리되어 있다. 그리고 도중 다리를 건설하는 쿼리에 대해 다음과 같은 답을 해주어야 한다.

1 i j : 섬i 와 섬j 간의 다리를 잇고 1을 출력하며, 만약 섬i와 섬j가 이미 어떤 경로를 통해 이동할 수 있다면 잇지 않고 0을 출력한다.

다리 공사 덕분에 민제는 섬과 섬사이를 이동할 수 있고, NYPC에서 받은 노트북을 이용해서 섬i 와 섬j를 잇는 최단경로상에 있는 여러가지를 알고 싶다.
하지만, 민제가 그 노트북을 서현중로에 놓고 왔기 때문에 지금은 계산할 수 없어 여러분에게 도움을 요청했다.
이런 이유로 여러분은 다음 쿼리를 처리해주어야 한다.

2 i j : 섬i와 섬j를 잇는 최단경로 상에 있는 물고기의 합을 구한다. 만약 최단경로가 여러 개 있다면, 아무 경로에서 출력한다. 만약 섬i와 섬j가 연결되지 않았다면 -1을 출력한다.

그런데 민제가 이동하면서 물고기의 수가 바뀌기 때문에, 다음과 같은 쿼리도 처리해주어야 한다.

3 i x : 섬i의 물고기 수가 x마리인것으로 바뀌었다. (1 <= x <= 100,000)
4 i k : 섬i와 연결된 모든 섬에 물고기가 k마리 추가되었다. (섬i 포함, 1 <= k <= 100,000)

Input

N
a_1 a_2 ... a_N (1 <= a_i <= 100,000)
Q (쿼리의 개수)
이후 Q개의 쿼리가 각 줄마다 주어진다.

Subtask
모든 태스크에 대해서 1 <= N <= 100,000, 1 <= Q <= 300,000이다.
#1 1번쿼리만 주어진다.
#2 1,2번 쿼리만 주어진다.
#3 1,2,3번 쿼리만 주어진다.
#4 1,2,3,4번 모든 쿼리가 주어진다.

Output

각 쿼리에 대한 답을 한 줄에 하나씩 출력한다.

IO Example

입력1)
3
1 2 3
4
1 1 2
1 1 3
1 2 3
1 1 2

출력1)
1
1
0
0

입력2)
3
1 2 3
8
1 1 2
2 1 3
1 1 3
2 1 3
1 2 3
3 1 5
2 1 3
2 2 3

출력2)
1
-1
1
4
0
8
10

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]