No.3517 Snake Kunekune Graph
タグ : / 解いたユーザー数 10
作問者 :
Germanium32
yt142857
Problem Statement
There is a simple undirected graph with $N$ vertices and $M$ edges. For $1 \leq i \leq N$, the integer $A_i$ is written on vertex $i$. For $1 \leq i \leq M$, edge $i$ connects vertices $U_i$ and $V_i$. A snake walks on this graph.
The position of the snake is represented by a sequence of $k$ vertices $(x_1,\dots ,x_k)$, in order from the head. The snake always satisfies the following conditions.
- For $1 \leq i \leq k-1$, vertices $x_i$ and $x_{i+1}$ are connected by an edge.
- $\displaystyle \max_{1 \leq i \leq k} A_{x_i} - \min_{1 \leq i \leq k} A_{x_i} \leq X$
The length of this snake is $k$. The vertices $x_1,\dots ,x_k$ do not need to be distinct.
The snake repeats moves of the following form.
- Choose one vertex $p$ adjacent to the vertex $x_1$ where the head is.
-
Then, the snake moves as follows according to its length.
- If the length of the snake is less than $K$, its length grows by $1$ at the head. The position of the snake becomes $(p, x_1, \dots , x_{k})$.
- If the length of the snake is $K$, its length shrinks by $1$ at the tail, and then grows by $1$ at the head. The position of the snake becomes $(x_1, \dots , x_{k-1})$, and then $(p, x_1, \dots , x_{k-1})$.
Find the number of $2$ distinct integers $1 \leq i, j \leq N$ satisfying the following condition.
- A snake of length $1$ at vertex $i$ can bring its head to vertex $j$ by repeating some number of moves.
Constraints
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq M \leq \min(\frac {N \times (N-1)}{2}, 2 \times 10^5)$
- $1 \leq X \leq 10^9$
- $2 \leq K \leq N$
- $1 \leq U_i, V_i \leq N$
- The given graph is simple.
- $1 \leq A_i \leq 10^9$
- All inputs are integers.
Input
$N\ M\ X \ K$ $A_1\ ... A_N$ $U_1\ V_1$ $\vdots$ $U_M\ V_M$
Output
Print a newline at the end.
Sample
Sample 1
Input
5 4 3 3 7 4 1 3 4 1 2 2 3 3 4 4 5
Output
14
The given graph is as shown in the figure below, with $X = 3$ and $K = 3$.
- The vertex reachable starting from vertex $1$ is $2$.
- The vertices reachable starting from vertex $2$ are $1,3,4,5$.
- The vertices reachable starting from vertex $3$ are $2,4,5$.
- The vertices reachable starting from vertex $4$ are $2,3,5$.
- The vertices reachable starting from vertex $5$ are $2,3,4$.
Therefore, the number of pairs to be found is $14$.
Sample 2
Input
5 4 3 2 7 4 1 3 4 1 2 2 3 3 4 4 5
Output
20
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。