問題一覧 > 通常問題

No.3093 Safe Infection

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 43
作問者 : RiRinbaru / テスター : hamo21 downer autumn09 ygussany
お気に入りにしたユーザー ProblemId : 11831 / 自分の提出
問題文最終更新日: 2025-04-06 13:27:09
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
QUPC2024 (順位表) の他の問題:

Problem Statement

There are $N$ people. There are $M$ friendships, given as a simple connected undirected graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. When edge $i(1≤i≤M)$ bidirectionally connects vertex $u_i$ and vertex $v_i$, it means that there is a friendship between $u_i$ and $v_i$.
A sequence $A={A_1, A_2, ..., A_N}$ is given. Person $i$ is infected with an infectious disease of level $A_i$.

You may perform the following operation any number of times, possibly 0 times.

  • For some $2$ people $A, B$ who have a friendship, let $a, b$ be the levels of the diseases they are respectively infected with. If $a>b$, replace $b$ with $a$. However, during this infection, if $a-b>K$, person $B$ cannot withstand the disease and dies.
Determine whether it is possible to reach a state where all people are alive and infected with a disease of the same level.

Input

$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)$
  • All inputs are integers.
  • The given graph is a simple connected undirected graph.

Output

If, by repeating the given operation, it is possible to reach a state where all people are alive and infected with a disease of the same level, print Yes; otherwise, print No.
Print a newline at the end.

Sample

Sample 1
Input
3 2 3
5 2 8
1 2
2 3
Output
Yes

Sample 2
Input
4 3 3
1 4 7 11
1 2
1 3
1 4
Output
No

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