結果

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

ソースコード

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
E=set()
for i in range(N):
  for j in G[i]:
    w=i*10**6+j
    E.add(w)
E=list(E)
K=len(E)
T={}
for i in range(K):
  T[E[i]]=i
Z=unif(K)
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][:]
    w0=T[i*10**6+pos]
    w1=T[pos*10**6+i]
    Z.unite(w0,w1)
    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]
      w1=T[a*10**6+i]
      w2=T[b*10**6+i]
      Z.unite(w1,w2)
      l=k
result=0
P=[[] for i in range(K)]
for i in range(N):
  for j in G[i]:
    if abs(A[i]-A[j])>X:
      continue
    w=T[i*10**6+j]
    pos=Z.root(w)
    P[pos].append((i,j))
for k in range(K):
  B=set()
  for Q in P[k]:
    a,b=Q[:]
    B.add(a)
    B.add(b)
  n=len(B)
  result+=n*(n-1)
print(result)
0