提出詳細

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

import sys
sys.setrecursionlimit(200000)

# UnionFind
class UnionFind:
    def __init__(self, n):
        self.par = [-1] * n
        self.S = n
    def root(self, A):
        if self.par[A] < 0:
            return A
        self.par[A] = self.root(self.par[A])
        return self.par[A]
    def same(self, A, B):
        return self.root(A) == self.root(B)
    def unite(self, A, B):
        a = self.root(A)
        b = self.root(B)
        if a == b:
            return False
        if self.par[a] > self.par[b]:
            a, b = b, a
        self.par[a] += self.par[b]
        self.par[b] = a
        self.S -= 1
        return True
    def size(self, A):
        return -self.par[self.root(A)]
    def size(self):
        return self.S

# 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 77
case5.txt RE 77
case6.txt RE 80
case9.txt RE 77
case10.txt RE 86
case11.txt RE 81
case13.txt RE 80
sample1.txt AC 16
89 RE