問題一覧 > 通常問題

No.3517 Snake Kunekune Graph

レベル : / AI推定難易度 : 2350 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 10
作問者 : aa36 / テスター : imabc yu23578 Yoyoyo8128 GaLLium Germanium32 yt142857
お気に入りにしたユーザー ProblemId : 13117 / 自分の提出
問題文最終更新日: 2026-10-25 12:31: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
yukicoder contest 497 聖光学院プログラミングコンテスト2026 day1 (順位表) の他の問題:

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