日本情報オリンピック 第2回 女性部門

2022年1月24日
情報オリンピック日本委員会

問題文

IOI 国には，1 から N までの番号が付けられた N 個の町と，1 から M までの番号が付けられた M 本の道がある．

それぞれの道は，タクシーでのみ通行可能である．道 i (1 ≦ i ≦ M) のタクシーは町 A_i と町 B_i を双方向に移動でき，そのタクシーの色は，C_i = 1 のとき赤色，C_i = 2 のとき青色である．タクシーには料金がかかり，乗車すると以下のように所持金が変化する．

• 乗車前の所持金を a 円とする．
• タクシーが赤色の場合，乗車後の所持金が a - 1 円になる．
• タクシーが青色の場合，乗車後の所持金が「a ÷ 2 を整数に切り捨てた値」円になる．

あなたは IOI 国の町 1 に住んでおり，以下の Q 個の質問の答えを知っておきたい．j 番目 (1 ≦ j ≦ Q) の質問は以下の通りである．

• 町 1 から出発し，1 円以上の所持金を残した状態で町 T_j に到着するために，最初に少なくとも何円の所持金を持っている必要があるか．ただし，答えが L 円よりも大きい場合は，代わりに Large と答えよ．

町とタクシーの情報，そして質問の内容が与えられたとき，すべての質問に答えるプログラムを作成せよ．

制約

• 2 ≦ N ≦ 200 000．
• N - 1 ≦ M ≦ 200 000．
• 1 ≦ Q ≦ 200 000．
• 1 ≦ L ≦ 1 000 000 000．
• 1 ≦ A_i ＜ B_i ≦ N (1 ≦ i ≦ M)．
• (A_i, B_i) ≠ (A_j, B_j) (1 ≦ i ＜ j ≦ M)．
• 1 ≦ C_i ≦ 2 (1 ≦ i ≦ M)．
• 2 ≦ T_j ≦ N (1 ≦ j ≦ Q)．
• どの町の間も，いくつかの道を通って行き来できる．
• 入力される値はすべて整数である．

小課題

1. (9 点) M = N - 1，(A_i, B_i) = (i, i + 1) (1 ≦ i ≦ M)，Q = 1，N ≦ 100，L ≦ 100．
2. (19 点) M = N - 1，(A_i, B_i) = (i, i + 1) (1 ≦ i ≦ M)，Q = 1．
3. (19 点) M = N - 1，(A_i, B_i) = (i, i + 1) (1 ≦ i ≦ M)．
4. (16 点) N ≦ 50 000，M ≦ 50 000，Q = 1，C_i = 1 (1 ≦ i ≦ M)．
5. (20 点) N ≦ 50 000，M ≦ 50 000，Q = 1．
6. (12 点) N ≦ 50 000，M ≦ 50 000，Q ≦ 50 000．
7. (5 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる．

各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力

入力は以下の形式で標準入力から与えられる．
N M Q L
A₁ B₁ C₁
A₂ B₂ C₂
:
A_M B_M C_M
T₁
T₂
:
T_Q

出力

標準出力に Q 行で出力せよ．j 行目 (1 ≦ j ≦ Q) には，j 番目の質問の答えを出力せよ．

入出力例

入力例 1
7 6 1 10
1 2 2
2 3 1
3 4 2
4 5 1
5 6 1
6 7 2
5

出力例 1
10

町 1 → 町 2 → 町 3 → 町 4 → 町 5 の経路で移動するならば，順に青，赤，青，赤のタクシーに乗ることになる．すると，最初に所持金が 10 円あった場合，所持金は 10 円 → 5 円 → 4 円 → 2 円 → 1 円となり，1 円以上を残した状態で町 5 に到着できる．

一方，最初の所持金が 9 円以下の場合，1 円以上を残した状態で町 5 に到着することはできない．

この入力例は小課題 1, 2, 3, 5, 6, 7 の制約を満たす．

入力例 2
10 9 3 25
1 2 2
2 3 1
3 4 1
4 5 1
5 6 2
6 7 1
7 8 1
8 9 1
9 10 2
10
9
3

出力例 2
Large
22
4

例えば，1 番目の質問について考えよう．

町 1 から出発して町 10 に移動するとき，町 1 → 町 2 → … → 町 9 → 町 10 の経路をたどることになる．しかし，最初に L (= 25) 円持っていたとしても，タクシーを使うごとに所持金が 25 円 → 12 円 → 11 円 → 10 円 → … と減っていき，1 円以上を残して町 10 にたどり着くことはできない．よって，Large と出力しなければならない．

この入力例は小課題 3, 6, 7 の制約を満たす．

入力例 3
5 6 1 1000000000
1 4 1
1 5 1
4 5 1
3 4 1
3 5 1
2 3 1
2

出力例 3
4

町 1 → 町 5 → 町 3 → 町 2 の経路で移動するならば，赤いタクシーに 3 回乗ることになる．すると，最初に所持金が 4 円あった場合，所持金は 4 円 → 3 円 → 2 円 → 1 円となり，1 円以上を残した状態で町 2 に到着できる．

一方，最初の所持金が 3 円以下の場合，1 円以上を残した状態で町 2 に到着することはできない．

この入力例は小課題 4, 5, 6, 7 の制約を満たす．

入力例 4
9 11 5 10
1 2 1
1 3 2
2 3 2
2 9 2
3 9 1
4 9 1
8 9 1
5 8 1
5 7 1
4 7 2
6 7 2
2
6
7
8
9

出力例 4
2
Large
7
5
3

この入力例は小課題 6, 7 の制約を満たす．