結果

問題 No.3517 Snake Kunekune Graph
コンテスト
ユーザー ゼット
提出日時 2026-04-27 20:32:06
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
RE  
実行時間 -
コード長 1,388 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 134 ms
コンパイル使用メモリ 85,376 KB
実行使用メモリ 119,680 KB
最終ジャッジ日時 2026-04-27 20:32:38
合計ジャッジ時間 29,345 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 1
other AC * 20 WA * 14 RE * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class unif:
  def __init__(self,n):
    self.pare=[-1]*n
    self.size=[1]*n
  def root(self,x):
    while self.pare[x]!=-1:
      x=self.pare[x]
    return x
  def unite(self,u,v):
    rootu=self.root(u)
    rootv=self.root(v)
    if rootu!=rootv:
      if self.size[rootu]>=self.size[rootv]:
        self.pare[rootv]=rootu
        self.size[rootu]+=self.size[rootv]
      else:
        self.pare[rootu]=rootv
        self.size[rootv]+=self.size[rootu]
  def same(self,s,t):
    return self.root(s)==self.root(t)
N,M,X,K=map(int,input().split())
if K==2:
  p=[1]
  print(p[1])
A=list(map(int,input().split()))
G=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
from bisect import bisect_right
Z=unif(N)
for i in range(N):
  x=A[i]
  L=[]
  h=[]
  for y in G[i]:
    z=A[y]
    L.append((z,y))
    h.append(z)
  L.sort()
  h.sort()
  l=0
  for j in range(len(L)):
    z,pos=L[j][:]
    if l<j:
      l=j
    if abs(z-x)>X:
      continue
    e=bisect_right(h,min(x,z)+X)
    for k in range(l+1,e):
      a,b=L[k-1][1],L[k][1]
      Z.unite(a,b)
      Z.unite(a,i)
      l=k
result=0
used=[False]*N
for i in range(N):
  pos=Z.root(i)
  if used[pos]==True:
    continue
  used[pos]=True
  n=Z.size[pos]
  result+=n*(n-1)
  for j in G[i]:
    if Z.same(i,j)==False:
      if abs(A[i]-A[j])<=X:
        result+=1
print(result)
0