問題一覧 > 通常問題

No.2674 k-Walk on Bipartite

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 78
作問者 : nu50218nu50218 / テスター : XelmephXelmeph nullnull ngtkanangtkana NokonoKotlinNokonoKotlin 👑 eoeoeoeo
4 ProblemId : 10651 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-15 21:22:03

問題文

グラフの頂点 $s, t$ に対して、「 $s$ から隣接頂点への移動を $k$ 回繰り返して $t$ へ移動する経路」のことを $s$ から $t$ への長さ $k$ の歩道と呼びます。

まず始めに、eoeo はこのような問題を考えました。

頂点集合 $V$ と辺集合 $E$ からなる単純無向二部グラフ $G$ 、その頂点 $s, t$、正整数 $k$ が与えられます。
グラフ $G$ に $s$ から $t$ への長さ $k$ の歩道が存在するか判定してください。

しかしこのままではシンプルすぎます。 nu50218 は上の問題に一捻り加えて、辺集合 $E$ の代わりに $E$ から $0$ 本以上の辺を削除した $F$ を入力として与えることにしました。 改変された以下の問題を解いてください。

単純無向二部グラフ $G$ の頂点数 $N$ 、辺集合の部分集合 $F \subseteq E$、頂点 $s, t$、正整数 $k$ が与えられます。

与えられた情報のみから、グラフ $G$ に $s$ から $t$ への長さ $k$ の歩道が

  • 存在すると確定するとき Yes
  • 存在しないと確定するとき No
  • 上記のいずれでもないとき Unknown

を出力してください。

形式的な問題文

より厳密には、グラフ $(V, F)$ を部分グラフとして含む任意の $N$ 頂点からなる単純無向二部グラフ $H$ について

  • 必ずグラフ $H$ に $s$ から $t$ への長さ $k$ の歩道が存在するとき Yes を、
  • 必ずグラフ $H$ に $s$ から $t$ への長さ $k$ の歩道が存在しないとき No

出力し、上記のいずれでもないとき Unknown を出力してください。

入力

入力は以下の形式で標準入力から与えられます。

グラフの $N$ 個の頂点はそれぞれ $1, 2, \dots, N$ と番号付けられています。

$M = |F|$ であり、 $A_i, B_i$ は $F$ の $i$ 本目の辺の端点です。

$N$ $M$
$s$ $t$ $k$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

出力

標準出力へ一行で出力し、最後に改行してください。

制約

入力は以下の制約を満たします。

  • 入力はすべて整数
  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq M \leq 2 \times 10^5$
  • $1 \leq s, t \leq N$
  • $1 \leq k \leq 10^9$
  • $1 \leq A_i < B_i \leq N$
  • $i \neq j$ ならば $(A_i, B_i) \neq (A_j, B_j)$
  • グラフ $(V, F)$ は二部グラフである

サンプル

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

辺集合 $E$ は、 $F$ または $F$ に 辺 $\{1, 4\}$ を加えたものです。 後者の場合、たとえば頂点 $1$ から頂点 $4$ への長さ $5$ の歩道として $1 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 4$ が存在します。

サンプル2
入力
4 3
1 3 3
1 2
2 3
3 4
出力
No

辺集合 $E$ は、 $F$ または $F$ に 辺 $\{1, 4\}$ を加えたものです。 いずれの場合も、頂点 $1$ から頂点 $3$ への長さ $3$ の歩道は存在しないことが示せます。

サンプル3
入力
4 3
1 4 1
1 2
2 3
3 4
出力
Unknown

辺集合 $E$ は、 $F$ または $F$ に 辺 $\{1, 4\}$ を加えたものです。 後者の場合、たとえば頂点 $1$ から頂点 $4$ への長さ $1$ の歩道として $1 \rightarrow 4$ が存在します。 一方で、前者の場合には存在しないことが示せます。

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