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

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

문제

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번

채점 및 기타 정보

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

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

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

한국어 | English (Beta)