第 040 场 AtCoder Beginner Contest
翻译中…
Problem Statement
翻译中…
ある国には $N$ 個の都市があり、それぞれ $1$ から $N$ までの番号がつけられています。これらの都市間を結ぶ $M$ 本の道路があり、$i$ 本目の道路は都市 $a_i$ と都市 $b_i$ を結ぶもので、$y_i$ 年に造られたものです。
翻译中…
この国の国民はとても心配性なので、あまりに古い道は事故の危険性が高いと考えて使わないことがあります。そこであなたは、この国の交通状況を調査することにしました。
翻译中…
$Q$ 人の国民の情報が与えられます。$j$ 人目の国民について、都市 $v_j$ に住んでおり、造られた年が $w_j$ 年以前 ($w_j$ 年ちょうども含む) であるような道路を使わないことがわかっています。
翻译中…
それぞれの国民に対し、その人が住んでいる都市から道路のみを使って行き来できるような都市の個数を求めてください。
翻译中…
Constraints
翻译中…
$1 ≦ N ≦ 100,000$$0 ≦ M ≦ 200,000$$1 ≦ a_i,b_i ≦ N$$a_i ≠ b_i$$1 ≦ y_i ≦ 200,000$$1 ≦ Q ≦ 100,000$$1 ≦ v_j ≦ N$$0 ≦ w_j ≦ 200,000$
翻译中…
部分点
翻译中…
$50$点分のテストケースでは、$N ≦ 1,000$,$M ≦ 2,000$,$Q ≦ 1,000$をみたす。
翻译中…
Input
翻译中…
入力は以下の形式で標準入力から与えられる。
翻译中…
N M
a_1 b_1 y_1
:
a_M b_M y_M
Q
v_1 w_1
:
v_Q w_Q翻译中…
Output
翻译中…
$Q$ 行出力せよ。そのうちの $j$ 行目には、$j$ 人目の国民が道路のみを使って行き来可能な都市の個数を出力せよ。
翻译中…
样例
Input #1
5 4
1 2 2000
2 3 2004
3 4 1999
4 5 2001
3
1 2000
1 1999
3 1995
Output #1
1
3
5
$Q$ 人それぞれの国民について、答えは以下のようになります。
- $1$ 人目は都市 $1$ に住んでおり、$2000$ 年以前に造られた道を使いません。都市 $1$ につながる唯一の道は $2000$ 年に造られているので、都市 $1$ 以外へ行くことができません。したがって答えは $1$ となります。
- $2$ 人目は都市 $1$ に住んでおり、都市 $2$ や $3$ へ行くことができます。しかし、$1999$ 年以前に造られた道を使わないので都市 $4$ へ行くことはできません。したがって答えは $3$ となります。
- $3$ 人目は $1995$ 年以前に造られた道を使いませんが、すべての道はそれより新しいため、すべての道をつかってすべての都市へ行くことができます。したがって答えは $5$ となります。
Input #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
Output #2
3
3
4
1
1
Input #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
Output #3
3
3
2
1
同じふたつの都市間を結ぶ道が $2$ 本以上あることや、すべての道を使っても辿り着けない都市がありうることに注意してください。
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。