問題一覧 > 通常問題

No.1340 おーじ君をさがせ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 117
作問者 : shinchanshinchan / テスター : 👑 maspymaspy
13 ProblemId : 5251 / 出題時の順位表
問題文最終更新日: 2020-12-30 22:20:36

問題文

$0$ から $N-1$ の番号がついた $N$ 個の頂点と、$0$ から $M-1$ の番号のついた $M$ 辺からなる有向グラフが与えられます。
おーじ君は初めに頂点 $0$ にいます。
時間が $1$ 秒進むたびに、おーじ君は今いる頂点から出ているいずれかの有向辺に従って、頂点を $1$ つ移動します。ただし、$0$ 秒後は移動しません。
$T+0.5$ 秒後におーじ君がいる可能性のある頂点の個数を求めてください。
ただし、移動する時点で頂点から有向辺が出ておらず、移動できなくなったおーじ君は消滅します。
また、移動は十分高速で、所要時間は無視できます。

このグラフには自己ループや多重辺が存在することがあり、連結とは限らないので注意してください。

入力

$N\ M\ T$
$a_1\ b_1 $
$a_2\ b_2 $ 
$:$
$a_M\ b_M$

  • $1 \leq N \leq 100$
  • $0 \leq M \leq 10000$
  • $0 \leq T \leq 10^{18}$
  • $2$ 行目から $M$ 行、グラフの $i$ 番目の有向辺が繋いでいる頂点の番号 $a_i$ と $b_i$ ($0\ \leq a_i,\ b_i\ < N$) が与えられる。 これは、$i$ 番目の辺が、 $a_i$ から $b_i$ に移動できる有向辺であることを表す。
  • 入力はすべて整数で与えられる。

出力

$T+0.5$ 秒後におーじ君がいる可能性のある頂点の個数を出力せよ。 最後に改行してください。

サンプル

サンプル1
入力
5 6 10
0 1
1 2
2 3
3 0
1 4
4 0
出力
5

$10.5$ 秒後にはどの頂点にも存在できます。
例えば、$10.5$ 秒後におーじ君が頂点 $3$ にいるのであれば、経路の $1$ つとして、$0→1→2→3→0→1→4→0→1→2→3$ とたどれば可能です。

サンプル2
入力
5 4 5
0 1
1 2
2 3
3 4
出力
0

$4.5$ 秒間は動けますが、行き止まりになって $5.5$ 秒間は動けません。おーじ君は $5$ 秒後に消滅します。

サンプル3
入力
1 1 10
0 0
出力
1

おーじ君は頂点 $0$ から動かないです。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。