No.3093 Safe Infection
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.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
hamo21