配点: 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 满足约束。