結果

問題 No.3517 Snake Kunekune Graph
コンテスト
ユーザー ゼット
提出日時 2026-04-29 18:23:13
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 711 ms / 2,000 ms
コード長 1,825 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 246 ms
コンパイル使用メモリ 84,864 KB
実行使用メモリ 205,844 KB
最終ジャッジ日時 2026-04-29 18:23:43
合計ジャッジ時間 26,279 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

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())
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 K==2:
      Z.unite(2*i,2*y)
      Z.unite(2*i,2*y+1)
      Z.unite(2*i+1,2*y)
      continue
    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
T={}
R=[set() for i in range(2*N)]
g=[-1]*(2*N)
for i in range(2*N):
  pos=Z.root(i)
  R[pos].add(i//2)
for i in range(N):
  a=Z.root(2*i)
  b=Z.root(2*i+1)
  if Z.size[a]>Z.size[b]:
    a,b=b,a
  if a==b:
    n=len(R[a])-1
    result+=n
  else:
    count=len(R[a])+len(R[b])-2
    w=a*10**10+b
    if w in T:
      n=T[w]
    else:
      for pos in R[a]:
        if pos==i:
          continue
        if pos in R[b]:
          count-=1
      T[w]=count
      n=count
    result+=n
print(result)
0