题目详情题解（0）讨论（0）提交记录（0）

AT_abc040_d.[ABC040D] 道路の老朽化対策について

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在某个国家有 NN 个城市，每个城市编号为 11 到 NN。这些城市之间有 MM 条道路，第 ii 条道路连接城市 aia_i 和城市 bib_i，并且是在 yiy_i 年修建的。

这个国家的国民非常担心安全，因此他们认为太老的道路有较高的事故风险，有时会选择不使用这些道路。现在你需要调查这个国家的交通状况。

给定 QQ 位国民的信息。对于第 jj 位国民，已知他住在城市 vjv_j，并且不会使用修建年份不晚于 wjw_j 年（即 wjw_j 年及以前）的道路。

对于每位国民，求出仅通过道路能够从他所居住的城市到达的城市数量。

输入格式

输入按以下格式从标准输入读入。

NN MM a1a_1 b1b_1 y1y_1 : aMa_M bMb_M yMy_M QQ v1v_1 w1w_1 : vQv_Q wQw_Q

输出格式

输出 QQ 行。第 jj 行输出第 jj 位国民仅通过道路能够到达的城市数量。

输入输出样例

  • 输入#1

    5 4
1 2 2000
2 3 2004
3 4 1999
4 5 2001
3
1 2000
1 1999
3 1995

    输出#1

    1
3
5

  • 输入#2

    4 5
1 2 2005
3 1 2001
3 4 2002
1 4 2004
4 2 2003
5
1 2003
2 2003
1 2001
3 2003
4 2004

    输出#2

    3
3
4
1
1

  • 输入#3

    4 5
1 2 10
1 2 1000
2 3 10000
2 3 100000
3 1 200000
4
1 0
2 10000
3 100000
4 0

    输出#3

    3
3
2
1

说明/提示

限制条件

  • 1≤N≤100, ⁣0001\leq N\leq 100,\!000
  • 0≤M≤200, ⁣0000\leq M\leq 200,\!000
  • 1≤ai,bi≤N1\leq a_i, b_i\leq N
  • ai≠bia_i\neq b_i
  • 1≤yi≤200, ⁣0001\leq y_i\leq 200,\!000
  • 1≤Q≤100, ⁣0001\leq Q\leq 100,\!000
  • 1≤vj≤N1\leq v_j\leq N
  • 0≤wj≤200, ⁣0000\leq w_j\leq 200,\!000

部分分

  • 对于 5050 分的测试点，满足 N≤1, ⁣000N\leq 1,\!000，M≤2, ⁣000M\leq 2,\!000，Q≤1, ⁣000Q\leq 1,\!000。

样例解释 1

对于每一位国民，答案如下：

  • 第 1 位国民住在城市 1，不会使用 20002000 年及以前修建的道路。城市 1 唯一连接的道路是在 20002000 年修建的，因此无法前往其他城市，答案为 11。
  • 第 2 位国民住在城市 1，可以前往城市 2 和 3。但不会使用 19991999 年及以前修建的道路，因此无法前往城市 4，答案为 33。
  • 第 3 位国民不会使用 19951995 年及以前修建的道路，但所有道路都比这更新，因此可以到达所有城市，答案为 55。

样例解释 3

请注意，可能存在两座城市之间有两条或以上的道路，也可能存在即使使用所有道路也无法到达的城市。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页