Problems
La Paz, the capital city of Bolivia, is famous as a tourist destination and for its aerial cable car, Mi Teleferico.
You are visiting La Paz for sightseeing and want to visit as many attractions as possible. In this task, we consider the following simplified situation.
There are N aerial cable car stations in La Paz, numbered 1 to N in order of increasing altitude.
There are M one-way lines, numbered 1 to M, and each line is operated by a single cable car company. The companies are numbered from 1 to P.
Line i (1 ≤ i ≤ M) runs from station Aᵢ to station Bᵢ and is managed by company Cᵢ. (It is guaranteed that Aᵢ < Bᵢ.)
The Bureau of Transportation of La Paz issues unlimited ride passes. Each ride pass consists of two integers l and r (1 ≤ l ≤ r ≤ P) and allows the holder to ride any line operated by a company with a number between l and r (inclusive). (A single pass can be used for multiple lines.)
There are Q tourists, numbered 1 to Q. Tourist j (1 ≤ j ≤ Q) initially has a ride pass (Lⱼ, Rⱼ) and Xⱼ boliviano cash.
Each tourist’s goal is to ensure that, using only the lines available with their ride pass, every station is reachable from station 1.
To achieve this, tourist j is allowed to exchange their ride pass once as follows:
Choose two integers l′ and r′ (1 ≤ l′ ≤ r′ ≤ P).
Exchange the current ride pass (Lⱼ, Rⱼ) for a new ride pass (l′, r′) at a cost of |Lⱼ − l′| + |Rⱼ − r′| boliviano.
Determine for each tourist whether they can achieve their goal within the cash amount Xⱼ they possess.
Input
The first line contains three integers N, M, and P.
The next M lines each contain three space-separated integers Aᵢ, Bᵢ, Cᵢ (for 1 ≤ i ≤ M), where Aᵢ and Bᵢ denote the starting and ending stations of line i, and Cᵢ is the company that manages the line.
The following line contains an integer Q.
The next Q lines each contain three space-separated integers Lⱼ, Rⱼ, and Xⱼ (for 1 ≤ j ≤ Q), where (Lⱼ, Rⱼ) is the ride pass initially held by tourist j, and Xⱼ is the cash they have in boliviano.
[Constrains]
2 ≤ N ≤ 300\ 000 1 ≤ M ≤ 300\ 000 1 \le P \le 10^9 0 ≤ A_i ≤ B_i \le N (1 ≤ i ≤ N )0 ≤ C_i ≤ P (1 ≤ i ≤ N )1 ≤ Q ≤ 400\ 000 1 ≤ L_j ≤ R_j \le P (1 ≤ j ≤ Q )0 ≤ X_i ≤ 10^9 (1 ≤ j ≤ Q )Given values are all integers.
Output
Print Q lines. On the j-th line (1 ≤ j ≤ Q), output "Yes" if tourist j can achieve their goal within the cash Xⱼ they have, or "No" otherwise.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 7 | N ≤ 50, M ≤ 50, Q ≤ 50, and Xⱼ = 0 for all j |
| #2 | 8 | P ≤ 10 |
| #3 | 11 | P ≤ 100 |
| #4 | 23 | P ≤ 300,000 and Xⱼ = 0 for all j |
| #5 | 9 | P ≤ 300,000 |
| #6 | 22 | N ≤ 8,000, M ≤ 8,000 |
| #7 | 20 | No additional constraints |
Example #1
4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
4
3 7 0
5 6 0
3 4 0
1 9 0
Yes
No
No
Yes
Tourist 1 has the ride pass (3, 7) and 0 boliviano. With this pass, they can ride lines 1, 2, 3, and 4, allowing travel from station 1 to all stations → Yes.
Tourist 2 has the ride pass (5, 6) and 0 cash, which only permits riding lines 3 and 4; thus, station 4 is unreachable → No.
Tourist 3 with ride pass (3, 4) and 0 cash cannot meet the goal → No.
Tourist 4 has the ride pass (1, 9) and 0 cash, enabling all lines to be ridden, so the goal is achievable → Yes.
Example #2
4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
3
5 6 10
3 4 1
7 8 3
Yes
No
Yes
Tourist 1, with initial ride pass (5, 6) and 10 boliviano, can exchange their pass to (1, 5) at a cost of 5 (|5−1|+|6−5|), which makes it possible to travel from station 1 to all stations → Yes.
Tourist 2, with ride pass (3, 4) and 1 boliviano, cannot achieve the goal via any exchange → No.
Tourist 3 can achieve the goal → Yes.
Example #3
3 1 1000000000
1 2 6
1
1 1000000000 1000000000
No
The given line does not allow travel from station 1 to station 3, so the tourist cannot achieve their goal regardless of the ride pass.
Example #4
5 9 2000
2 3 1814
2 3 457
1 2 1226
3 4 1354
1 5 1050
1 2 1725
2 3 1383
1 5 1626
1 4 1795
5
850 1872 128
82 428 1217
487 924 573
1639 1926 202
202 420 25
Yes
Yes
Yes
Yes
No
Each tourist evaluates whether, with or without a pass exchange (subject to their available cash), they can obtain a ride pass that allows travel from station 1 to every station. The outputs indicate the feasibility for each tourist.
You must sign in to write code.