問題一覧 > 通常問題

No.3093 Safe Infection

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 48
作問者 : RiRinbaru / テスター : hamo21 downer autumn09 👑 ygussany
3 ProblemId : 11831 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-04-06 13:27:09

問題文

$N$ 人の人間がいます。$M$ 組の交友関係があり、それぞれの交友関係は頂点に $1$ から $N$ の番号が、辺に $1$ から $M$ の番号が付いた $N$ 頂点 $M$ 辺の単純連結無向グラフとして与えられ、辺$i(1≤i≤M)$ が頂点 $u_i$ と頂点 $v_i$ を双方向に結んでいるとき、$u_i$ と $v_i$ の間には交友関係があることを表します。
数列 $A={A_1, A_2, ..., A_N}$ が与えられます。人 $i$ はレベル $A_i$ の感染症にかかっています。

あなたは以下の操作を0回以上任意の回数行うことができます。

  • 交友関係を持つある $2$ 人 $A, B$ について、それぞれの感染している感染症のレベルを $a, b$ としたときに、$a>b$ であるならば $b$ を $a$ に置き換える。ただし感染の際、$a-b>K$ であるならば人 $B$ は感染症に耐えきれず死んでしまう。
すべての人間が生きていて、かつ同じレベルの感染症にかかっている状態になるかどうかを判定してください。

入力

$N\ M\ K$
$A_1\ A_2\ ...\ A_N$
$u_1\ v_1$
$u_2\ v_2$
$:$
$u_M\ v_M$
  • $1\leq N \leq10^5$
  • $1\leq M\leq 10^5$
  • $1\leq K\leq 10^9$
  • $0\leq A_i\leq 10^9(1\leq i\leq N)$
  • $1\leq u_i< v_i\leq N(1\leq i\leq M)$
  • 入力はすべて整数
  • 与えられるグラフは単純連結無向グラフです。

出力

与えられた操作を繰り返すことで、すべての人間が、生存しておりかつ同じレベルの感染症にかかっている状態にできるならばYesを、そうでなければNoを出力してください。
最後に改行してください。

サンプル

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

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

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