提出詳細

提出id	提出時刻	ユーザー名	問題	言語	判定状況	判定	実行時間
114841	2023-10-24 08:48:40	hiikunZ	J	python	11/11	RE	89

import sys
sys.setrecursionlimit(200000)

# UnionFind
# https://algo-method.com/descriptions/136
class UnionFind():
    # 初期化
    def __init__(self, n):
        self.par = [-1] * n
        self.rank = [0] * n
        self.siz = [1] * n

    # 根を求める
    def root(self, x):
        if self.par[x] == -1: return x # x が根の場合は x を返す
        else:
          self.par[x] = self.root(self.par[x]) # 経路圧縮
          return self.par[x]

    # x と y が同じグループに属するか (根が一致するか)
    def issame(self, x, y):
        return self.root(x) == self.root(y)

    # x を含むグループと y を含むグループを併合する
    def unite(self, x, y):
        # x 側と y 側の根を取得する
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry: return False # すでに同じグループのときは何もしない
        # union by rank
        if self.rank[rx] < self.rank[ry]: # ry 側の rank が小さくなるようにする
            rx, ry = ry, rx
        self.par[ry] = rx # ry を rx の子とする
        if self.rank[rx] == self.rank[ry]: # rx 側の rank を調整する
            self.rank[rx] += 1
        self.siz[rx] += self.siz[ry] # rx 側の siz を調整する
        return True
    
    # x を含む根付き木のサイズを求める
    def size(self, x):
        return self.siz[self.root(x)]
# main
N, M, X, P = map(int, input().split())
B = list(map(int, input().split()))
T = list(map(int, input().split()))
# assert(1 <= N and N <= 100)
# assert(1 <= M and M <= 100000)
# assert(1 <= X and X <= 100000)
# assert(1 <= P and P <= 1000000000)
# assert(len(B) == N)
# assert(len(T) == M)
#for i in range(N):
#    assert(1 <= B[i] and B[i] <= 1000000000)
#for i in range(M):
#    assert(1 <= T[i] and T[i] <= 1000000000)
UF = UnionFind(M + 100)
while True:
    try:
        u, v = map(int, input().split())
        #assert(1 <= u and u <= M)
        #assert(1 <= v and v <= M)
        u -= 1
        v -= 1
        UF.unite(u, v)
    except:
        break

ok = True
try:
    u,v = map(int, input().split())
    ok = False
except:
    pass

assert(ok)

ans = 0
for i in range(M):
    dis = 10**18
    for j in range(N):
        dis = min(dis, abs(B[j] - T[i]))
    if dis <= P:
        if UF.unite(i, M):
            ans += 1
print(ans)

case1.txt AC 18
case2.txt RE 89
case3.txt RE 85
case4.txt RE 78
case5.txt RE 76
case6.txt RE 83
case9.txt RE 77
case10.txt RE 83
case11.txt RE 80
case13.txt RE 80
sample1.txt AC 17
89 RE