問題一覧 > 通常問題

No.1400 すごろくで世界旅行

レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / 通常問題
タグ : / 解いたユーザー数 23
作問者 : CuriousFairy315CuriousFairy315 / テスター : yosswi414yosswi414
1 ProblemId : 3785 / 出題時の順位表
問題文最終更新日: 2021-02-19 07:38:10

問題文

315さんは一人ボードゲームで遊んでいます。
このボードゲームでは $V$ 個の頂点と1個の駒、 $V \times V$ の大きさの格子に区切られた紙を用いて遊びます。
紙には数字が書かれており、上から $i$ 番目、左から $j$ 番目のマスに書かれた数字は $E_{i,j}$ です。
駒が頂点 $i$ に置かれており、 $E_{i,j}=1$ ならば、次のターンに駒を頂点 $j$ に動かすことができます。
315さんは毎ターン必ず駒を動かさなくてはいけません。
この時、適切に駒を動かすことでどの頂点に駒が置かれた状態から開始しても $D$ ターン後に駒が置かれている頂点をどの頂点でも好きに選べるならばYesを、そうでないならNoを出力してください。
もし駒の置き方と動かし方によっては途中で駒を動かせなくなる場合は、Noを出力してください。

入力

$V\ D$
$E_{1,1}\ \cdots\ E_{1,V}$
$\vdots$
$E_{V,1}\ \cdots\ E_{V,V}$

  • $1 \leq V \leq 2000$
  • $1 \leq D \leq 10^{18}$
  • $E_{i,j}$ は $0$ か $1$ であり、 $E_{i,j}=1$ の時は頂点 $i$ から頂点 $j$ へ駒を1ターンで移動できることを表す
  • $E_{i,j}=E_{j,i}$
  • 入力は全て整数である

出力

条件を満たすならYesを、満たさないならNoを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3 3
011
101
110
出力
Yes

すごろくで世界旅行 (構築)の方で用いたサンプルと同一です。

サンプル2
入力
6 5
000111
000111
000111
111000
111000
111000
出力
No

完全二部グラフ$K_{3,3}$です。二部グラフでは制約を満たさないことがすぐに確認できます。

サンプル3
入力
5 640000
00100
00100
11111
00100
00100
出力
Yes

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