No.3756 Udon Network
About This Problem
This problem was created by the Kosen Competitive Programming Server for a promotional flyer to be distributed at an event called Kosen Procon. Whether you are a kosen student or not, please feel free to give it a try!
A rough editorial is available in the editorial section on yukicoder, and if time permits, we may also write an editorial article for people with no competitive programming experience.
Problem image for the event (click to open)
About the Difficulty
This problem has subtasks so that everyone from beginners to advanced competitors can enjoy it.
The estimated difficulty of each Subtask, converted to AtCoder Difficulty, is as follows.
- Subtask1: Gray
- Subtask2: Brown
- Subtask3: Green
- Subtask4: Cyan
- Subtask5: Blue
- Subtask6 (full score): Yellow
For all Subtasks, we have confirmed that the intended solutions are accepted in both C++23 and Python(PyPy3). However, some Subtasks have a tight time limit for Python(PyPy3), so even with the same time complexity, some implementations may get TLE. In that case, we recommend converting your program to C++, for example with generative AI.
Problem Statement
In Prefecture K, where Kosen Taro lives, there are $N$ udon shops and $M$ roads. Udon shop $i\ (1 \le i \le N)$ belongs to chain $A_i$, and road $j$ $(1 \le j \le M)$ bidirectionally connects shop $u_j$ and shop $v_j$.
In Prefecture K, each road is also assigned an integer value called its pilgrimage level. Road $j$ is assigned pilgrimage level $w_j$, and only people who have a pilgrimage level of at least $w_j$ can pass through this road.
You are given $Q$ queries; solve the following problem for each of them. The $k\ (1 \le k \le Q)$-th query is as follows.
You are given integers $s_k,c_k$.
Starting from shop $s_k$, Taro visits all reachable udon shops and collects the udon of the chain each shop belongs to.
Find the minimum pilgrimage level required for Taro to collect udon from at least $c_k$ different chains. However, if it is impossible for Taro to collect udon from at least $c_k$ different chains no matter how high his pilgrimage level is, output
-1.
Input
$N\ M\ Q$
$A_1\ A_2\ \cdots\ A_N$
$u_1\ v_1\ w_1$
$u_2\ v_2\ w_2$
$\vdots$
$u_M\ v_M\ w_M$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$
The $k$-th query $\text{query}_k$ is given in the following format.
$s_k\ c_k$
Constraints
- All input values are integers
- $1 \le N \le 2\times 10^5$
- $0 \le M \le 2\times 10^5$
- $1 \le Q \le 2\times 10^5$
- $1 \le A_i \le N$
- $1 \le u_j,\ v_j \le N$
- $1 \le w_j \le 10^9$
- $1 \le s_k,\ c_k \le N$
- Any $2$ shops can be traveled between by passing through some roads
- There are never $2$ or more roads directly connecting the same $2$ shops
Output
Output the answer to each query, separated by newlines.
Also add a newline at the end of the last line of output.
Partial Score
This problem has partial scoring based on subtasks.
| Subtask | Score | Constraints |
|---|---|---|
| Subtask $1$ | 2% (8 pts) | $N,M,Q \le 20$ |
| Subtask $2$ | 4% (16 pts) | $N,M \le 1000,\ Q \le 5000$ |
| Subtask $3$ | 8% (32 pts) | $s_k = 1$ |
| Subtask $4$ | 16% (64 pts) | $c_k \le 2$ |
| Subtask $5$ | 32% (128 pts) | $A_i = i$ |
| Subtask $6$ | 38% (152 pts) | 追加制約なし |
The constraints of each Subtask do not necessarily inherit the constraints of the preceding Subtasks. For example, a test case satisfying the constraints of Subtask $3$ does not necessarily satisfy the constraints of Subtask $2$.
Test cases are run in ascending order of Subtask number. Due to a limitation of yukicoder, judging is aborted as soon as a TLE occurs, so we recommend making your program terminate on Subtasks it does not target, for example by using the assert function, as needed.
Note that you get AC by passing all Subtasks.
Sample
Sample 1
Input
4 5 2 1 2 3 3 1 2 3 2 3 4 3 4 3 4 1 7 1 3 2 1 2 1 3
Output
2 3
This input satisfies the constraints of Subtasks $1,2,3,6$.
The input can be illustrated as follows. The number written on each vertex in the figure represents the chain that shop belongs to. The blue vertex represents the starting point, and the red vertices represent the vertices reachable from the starting point.
Illustration of the sample input (click to open)
- Query $1$
The blue vertex ( $s_1=1$ ) is the starting point. When the pilgrimage level is $D=2$, the blue and red vertices belong to at least $c_1=2$ different chains. With $D<2$, it is not possible to collect at least $2$ different chains, so output $2$, the minimum pilgrimage level satisfying the condition.
- Query $2$
The blue vertex ( $s_2=1$ ) is the starting point. When the pilgrimage level is $D=3$, the blue and red vertices belong to at least $c_2=3$ different chains. Here, there are $4$ reachable vertices in total, but note that what matters is not the number of vertices but the number of different chains those vertices belong to. With $D<3$, it is not possible to collect at least $3$ different chains, so output $3$, the minimum pilgrimage level satisfying the condition.
Sample 2
Input
8 10 6 1 2 3 4 5 6 7 8 1 2 132333 1 7 13100 4 3 108976 5 6 3911 1 4 55714 4 5 1629 2 8 59400 8 7 135765 2 3 79481 6 7 115502 1 2 7 2 5 2 5 3 5 6 5 8
Output
13100 13100 1629 3911 108976 108976
This input satisfies the constraints of Subtasks $1,2,5,6$.
Illustration of the sample input (click to open)
This year's Kosen Procon will be held in Kagawa Prefecture.
About the image
Original image (Wikipedia): Monaneko /
CC BY-SA 3.0
The original image has been modified for use.
Sample 3
Input
1 0 1 1 1 1
Output
0
This input satisfies the constraints of all Subtasks.
Note that the udon of the starting shop can also be collected.
Sample 4
Input
16 19 5 6 11 9 12 12 8 3 12 3 14 2 12 16 8 9 4 3 15 496513734 3 10 221107446 3 16 526825332 3 11 800915964 10 14 569184838 4 15 653916233 13 16 234134147 12 14 205768486 2 10 921532315 8 15 825947957 4 9 632723847 1 15 365777683 6 9 572312537 3 5 731148890 7 10 37197809 1 11 251721087 10 12 77987919 9 10 142437714 6 14 57202237 1 13 6 10 9 3 9 11 3 16
Output
-1 921532315 142437714 -1 -1
This input satisfies the constraints of Subtasks $1,2,6$.
Sample 5
Input
15 14 15 10 4 14 13 7 7 4 6 13 2 5 4 15 14 11 4 14 18416279 4 6 508296217 4 15 170711604 1 15 382401200 6 8 819754912 6 11 481535667 2 14 612834952 8 13 588801115 2 5 427235646 1 9 262676442 7 8 694213369 5 12 513030814 3 6 772381404 10 12 449299186 6 15 10 1 10 3 4 8 1 12 13 8 10 5 5 13 4 3 6 5 2 1 5 8 4 11 8 13 10 7
Output
-1 0 513030814 612834952 -1 819754912 612834952 -1 170711604 508296217 0 612834952 -1 -1 612834952
This input satisfies the constraints of Subtasks $1,2,6$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
tsunamayo123