Time Limit: 4 sec / Memory Limit: 1024 MB
配点: 100 点
問題文
IOI 国には,1 から N までの番号が付けられた N 個の町と,1 から M までの番号が付けられた M 本の道がある.
それぞれの道は,タクシーでのみ通行可能である.道 i (1 \leqq i \leqq M) のタクシーは町 A_i と町 B_i を双方向に移動でき,そのタクシーの色は,C_i = 1 のとき赤色,C_i = 2 のとき青色である.タクシーには料金がかかり,乗車すると以下のように所持金が変化する.
- 乗車前の所持金を a 円とする.
- タクシーが赤色の場合,乗車後の所持金が a - 1 円になる.
- タクシーが青色の場合,乗車後の所持金が「a \div 2 を整数に切り捨てた値」円になる.
あなたは IOI 国の町 1 に住んでおり,以下の Q 個の質問の答えを知っておきたい.j 番目 (1 \leqq j \leqq Q) の質問は以下の通りである.
- 町 1 から出発し,1 円以上の所持金を残した状態で町 T_j に到着するために,最初に少なくとも何円の所持金を持っている必要があるか.ただし,答えが L 円よりも大きい場合は,代わりに
Large
と答えよ.
町とタクシーの情報,そして質問の内容が与えられたとき,すべての質問に答えるプログラムを作成せよ.
制約
- 2 \leqq N \leqq 200\,000.
- N - 1 \leqq M \leqq 200\,000.
- 1 \leqq Q \leqq 200\,000.
- 1 \leqq L \leqq 1\,000\,000\,000.
- 1 \leqq A_i \lt B_i \leqq N (1 \leqq i \leqq M).
- (A_i, B_i) \neq (A_j, B_j) (1 \leqq i \lt j \leqq M).
- 1 \leqq C_i \leqq 2 (1 \leqq i \leqq M).
- 2 \leqq T_j \leqq N (1 \leqq j \leqq Q).
- どの町の間も,いくつかの道を通って行き来できる.
- 入力される値はすべて整数である.
小課題
- (9 点) M = N - 1,(A_i, B_i) = (i, i + 1) (1 \leqq i \leqq M),Q = 1,N \leqq 100,L \leqq 100.
- (19 点) M = N - 1,(A_i, B_i) = (i, i + 1) (1 \leqq i \leqq M),Q = 1.
- (19 点) M = N - 1,(A_i, B_i) = (i, i + 1) (1 \leqq i \leqq M).
- (16 点) N \leqq 50\,000,M \leqq 50\,000,Q = 1,C_i = 1 (1 \leqq i \leqq M).
- (20 点) N \leqq 50\,000,M \leqq 50\,000,Q = 1.
- (12 点) N \leqq 50\,000,M \leqq 50\,000,Q \leqq 50\,000.
- (5 点) 追加の制約はない.
採点に関する注意
すべての提出はジャッジシステム上で採点される.
提出されたソースコードは,小課題に対応するすべての採点用入力データについて正しい結果を返したとき,その小課題について正解と認められる.
各提出の得点は,提出されたソースコードについて正解と認められた小課題の得点の合計である.
この課題の得点は,この課題に対するすべての提出の得点の最大値である.
現在の得点は「提出結果」タブの「自分の得点状況」から確認できる.
入力
入力は以下の形式で標準入力から与えられる.
N M Q L A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M T_1 T_2 \vdots T_Q
出力
標準出力に Q 行で出力せよ.j 行目 (1 \leqq j \leqq 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 の制約を満たす.