Logo
(追記) (追記ここまで)

27992번 - Two Currencies 서브태스크다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB143555038.168%

문제

There are $N$ cities in JOI Kingdom, numbered from 1ドル$ to $N$. There are $N -1$ roads in JOI Kingdom, numbered from 1ドル$ to $N - 1$. The road $i$ (1ドル ≤ i ≤ N - 1$) connects the city $A_i$ and the city $B_i$ bi-directionally. It is possible to travel from any city to any other city by passing through some of the roads.

There are checkpoints on some of the roads in JOI Kingdom. There are $M$ checkpoints, numbered from 1ドル$ to $M$. The checkpoint $j$ (1ドル ≤ j ≤ M$) is located on the road $P_j$. In order to pass through it, you need to pay either one gold coin or $C_j$ silver coins.

There are $Q$ citizens in JOI Kingdom, numbered from 1ドル$ to $Q$. The citizen $k$ (1ドル ≤ k ≤ Q$) has $X_k$ gold coins and $Y_k$ silver coins, and wants to travel from the city $S_k$ to the city $T_k$. Since gold coins are valuable, all the citizens want to keep as many gold coins as possible.

Write a program which, given information of the cities, the roads, the checkpoints, and the citizens in JOI Kingdom, for each $k$ (1ドル ≤ k ≤ Q$), determines whether it is possible for the citizen $k$ to travel from the city $S_k$ to the city $T_k,ドル and, if it is possible, calculates the maximum possible number of gold coins the citizen $k$ can keep.

입력

Read the following data from the standard input.

$N$ $M$ $Q$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_{N-1}$ $B_{N-1}$

$P_1$ $C_1$

$P_2$ $C_2$

$\vdots$

$P_M$ $C_M$

$S_1$ $T_1$ $X_1$ $Y_1$

$S_2$ $T_2$ $X_2$ $Y_2$

$\vdots$

$S_Q$ $T_Q$ $X_Q$ $Y_Q$

출력

Write $Q$ lines to the standard output. In the $k$-th line (1ドル ≤ k ≤ Q$), if the citizen $k$ can travel from the city $S_k$ to the city $T_k,ドル output the maximum possible number of gold coins the citizen $k$ can keep. Otherwise, output $-1$ in the $k$-th line.

제한

  • 2ドル ≤ N ≤ 100,000円$.
  • 1ドル ≤ M ≤ 100,000円$.
  • 1ドル ≤ Q ≤ 100,000円$.
  • 1ドル ≤ A_i ≤ N$ (1ドル ≤ i ≤ N - 1$).
  • 1ドル ≤ B_i ≤ N$ (1ドル ≤ i ≤ N - 1$).
  • It is possible to travel from any city to any other city by passing through some of the roads.
  • 1ドル ≤ P_j ≤ N - 1$ (1ドル ≤ j ≤ M$).
  • 1ドル ≤ C_j ≤ 10^9$ (1ドル ≤ j ≤ M$).
  • 1ドル ≤ S_k ≤ N$ (1ドル ≤ k ≤ Q$).
  • 1ドル ≤ T_k ≤ N$ (1ドル ≤ k ≤ Q$).
  • $S_k \ne T_k$ (1ドル ≤ k ≤ Q$).
  • 0ドル ≤ X_k ≤ 10^9$ (1ドル ≤ k ≤ Q$).
  • 0ドル ≤ Y_k ≤ 10^{18}$ (1ドル ≤ k ≤ Q$).
  • Given values are all integers.

서브태스크

번호배점제한
110

$N ≤ 2,000円,ドル $M ≤ 2,000円,ドル $Q ≤ 2,000円$.

228

$C_1 = C_2 = \cdots = C_M$.

330

$A_i = i,ドル $B_i = i + 1$ (1ドル ≤ i ≤ N - 1$).

432

No additional constraints.

예제 입력 1 

5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1

예제 출력 1 

1
2
-1

The citizen 1ドル$ can travel from the city 3ドル$ to the city 4ドル$ as follows. After the travel, the citizen 1ドル$ keeps one gold coin.

  1. The citizen 1ドル$ travels from the city 3ドル$ to the city 1ドル$ by passing through the road 2ドル$. There are the checkpoints 1ドル,ドル 2ドル$ on the road 2ドル$. The citizen 1ドル$ pays one gold coin at the checkpoint 1ドル$ and passes through it, and 4ドル$ silver coins at the checkpoint 2ドル$ and passes through it, respectively. After that, the citizen 1ドル$ keeps one gold coin and 7ドル$ silver coins.
  2. The citizen 1ドル$ travels from the city 1ドル$ to the city 2ドル$ by passing through the road 1ドル$. Since there is no checkpoint on the road 1, the citizen 1ドル$ keeps one gold coin and 7ドル$ silver coins.
  3. The citizen 1ドル$ travels from the city 2ドル$ to the city 4ドル$ by passing through the road 3ドル$. There is the checkpoint 3ドル$ on the road 3ドル$. The citizen 1ドル$ pays 5ドル$ silver coins at the checkpoint 3ドル$ and passes through it. After that, the citizen 1ドル$ keeps one gold coin and 2ドル$ silver coins.

Since it is impossible for the citizen 1ドル$ to travel by finally keeping more than or equal to 2ドル$ gold coins, output 1ドル$ in the first line.

The citizen 2ドル$ can travel from the city 5ドル$ to the city 3ドル$ as follows. After the travel, the citizen 2ドル$ keeps two gold coins.

  1. The citizen 2ドル$ travels from the city 5ドル$ to the city 2ドル$ by passing through the road 4ドル$. There is the checkpoint 4ドル$ on the road 4ドル$. The citizen 2ドル$ pays one gold coin at the checkpoint 4ドル$ and passes through it. After that, the citizen 2ドル$ keeps 3ドル$ gold coins and 5ドル$ silver coins.
  2. The citizen 2ドル$ travels from the city 2ドル$ to the city 1ドル$ by passing through the road 1ドル$. Since there is no checkpoint on the road 1ドル,ドル the citizen 2ドル$ keeps 3ドル$ gold coins and 5ドル$ silver coins.
  3. The citizen 2ドル$ travels from the city 1ドル$ to the city 3ドル$ by passing through the road 2ドル$. On the road 2ドル,ドル there are the checkpoints 1ドル,ドル 2ドル$. The citizen 2ドル$ pays one gold coin at the checkpoint 1ドル$ and passes through it, and 4ドル$ silver coins at the checkpoint 2ドル$ and passes through it, respectively. After that, the citizen 2ドル$ keeps 2ドル$ gold coins and one silver coin.

Since it is impossible for the citizen 2ドル$ to travel by finally keeping more than or equal to 3ドル$ gold coins, output 2ドル$ in the second line.

Since it is impossible for the citizen 3ドル$ to travel from the city 2ドル$ to the city 3ドル,ドル output $-1$ in the third line.

This sample input satisfies the constraints of Subtasks 1, 4.

예제 입력 2 

10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3

예제 출력 2 

3
6
6
7
7
3
1
2
2

This sample input satisfies the constraints of Subtasks 1, 2, 4.

예제 입력 3 

8 7 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 4
3 7
2 10
5 2
4 1
4 4
5 6
6 3 7 69
7 1 5 55
3 1 6 8
8 2 5 45
4 6 4 45
6 1 3 33
2 1 0 19
3 7 2 31
7 1 2 31
7 2 4 58
8 3 5 63

예제 출력 3 

7
5
5
5
4
2
0
2
1
4
5

This sample input satisfies the constraints of Subtasks 1, 3, 4.

예제 입력 4 

8 7 11
1 8
1 4
3 1
3 6
6 7
2 1
5 2
5 5
5 8
4 7
6 6
4 1
6 4
1 7
4 7 2 18
2 4 5 1
4 2 1 32
1 5 7 21
2 5 0 50
8 4 4 33
1 7 6 16
4 8 7 18
1 2 8 13
5 4 10 42
7 1 6 40

예제 출력 4 

1
3
1
7
0
4
5
7
8
10
6

This sample input satisfies the constraints of Subtasks 1, 4.

힌트

출처

Camp > JOI Spring Training Camp > JOI 2022/2023 Spring Training Camp 1-1번

채점 및 기타 정보

  • 예제는 채점하지 않는다.
(追記) (追記ここまで)

출처

대학교 대회

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

AltStyle によって変換されたページ (->オリジナル) /