結果

問題 No.3517 Snake Kunekune Graph
コンテスト
ユーザー aa36
提出日時 2026-03-28 09:42:42
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 729 ms / 2,000 ms
コード長 1,369 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 253 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 165,232 KB
最終ジャッジ日時 2026-04-24 20:51:02
合計ジャッジ時間 29,958 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# python に 翻訳 https://yukicoder.me/submissions/1153828
N, M, X, K = map(int, input().split())# DSU
# DSU の部分
par = [-1] * (N * 2)
def leader(a):
   if par[a] < 0: return a
   else: 
      par[a] = leader(par[a])
      return par[a]
def merge(a, b) :
   x = leader(a); y = leader(b);
   if x == y: return x
   if -par[x] < -par[y]: x, y = y, x
   par[x] += par[y]
   par[y] = x
   return
   
   
A = list(map(int, input().split()))
plus = [1<<40] * N
minus = [0] * N
for i in range(M):
   u, v = map(int, input().split())
   u -= 1
   v -= 1
   if A[u] > A[v]: u,v = v,u
   if A[v] - A[u] <= X: merge(u, v + N)
   plus[u] = min(plus[u], A[v])
   minus[v] = max(minus[v], A[u])
for i in range(N):
   if K == 2 or plus[i] - minus[i] <= X: merge(i, i+N)
   
G = [[] for i in range(2*N)]
rG = [[] for i in range(N)]
for i in range(N):
   x0 = leader(i)
   x1 = leader(i + N)
   if x0 > x1: x0, x1 = x1, x0
   if x0 == x1:
      rG[i] = [x0]
      G[x0].append(i)
   else:
      rG[i] = [x0, x1]
      G[x0].append(i)
      G[x1].append(i)
from collections import defaultdict
cnt = defaultdict(int)
ans = 0
for i in range(N):
   if len(rG[i]) == 2: cnt[rG[i][0] * (1<<44) + rG[i][1]] += 1
for i in range(N):
   if len(rG[i]) == 1: ans += len(G[rG[i][0]]) - 1
   else: ans += len(G[rG[i][0]]) + len(G[rG[i][1]]) - cnt[rG[i][0] * (1<<44) + rG[i][1]] - 1
print(ans)
0