問題一覧 > 通常問題

No.3756 Udon Network

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 16
作問者 : tsunamayo123 / テスター : 👑 qand Yukkku Jikky1618 Misodango Blueberry
お気に入りにしたユーザー ProblemId : 14004 / 自分の提出
問題文最終更新日: 2026-10-09 12:33:14
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Kosen Competitive Programming Server

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.

SubtaskScoreConstraints
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もしくは右上の雲マークをクリックしてアカウントを作成してください。