結果

問題 No.3517 Snake Kunekune Graph
コンテスト
ユーザー ゼット
提出日時 2026-04-29 18:02:31
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
RE  
実行時間 -
コード長 1,431 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 247 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 186,444 KB
最終ジャッジ日時 2026-04-29 18:02:52
合計ジャッジ時間 19,850 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 1
other AC * 19 WA * 15 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())
  if abs(A[a-1]-A[b-1])<=X:
    G[a-1].append(b-1)
    G[b-1].append(a-1)
from bisect import bisect_right
Z=unif(2*N)
for i in range(N):
  x=A[i]
  L0=[]
  L1=[]
  p0=[]
  p1=[]
  for y in G[i]:
    if A[y]<A[i]:
      L0.append(y)
      p0.append(A[y])
    elif A[y]>A[i]:
      L1.append(y)
      p1.append(A[y])
    else:
      L0.append(y)
      p0.append(A[y])
      L1.append(y)
      p1.append(A[y])
  for pos in L0:
    Z.unite(2*pos,2*i+1)
  for pos in L1:
    Z.unite(2*pos+1,2*i)
  if len(L0)*len(L1):
    if min(p1)-max(p0)<=X:
      Z.unite(2*i,2*i+1)
result=0
used=[False]*(2*N)
R=[set() for i in range(2*N)]
for i in range(2*N):
  pos=Z.root(i)
  R[pos].add(i//2)
for i in range(2*N):
  n=len(R[i])
  result+=n*(n-1)
print(result)
0