本地能跑没问题,但是提交为什么全是RE,题目是P2504-聪明的猴子
import math
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.cot = n
def find(self,x):
if x==self.parent[x]:
return x
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX == rootY:
return False
self.parent[rootX] = rootY
self.cot -= 1
return True
def main():
m = int(input().strip())
sec = input().strip().split(' ')
mj = [0]*m
for i in range(m):
mj[i] = int(sec[i])
n = int(input().strip())
points = []
for _ in range(n):
cur = input().strip().split(" ")
x,y = int(cur[0]),int(cur[1])
points.append((x,y))
edges = []
for i in range(n):
for j in range(i+1,n):
edges.append((i,j, math.sqrt((points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2)))
edges.sort(key=lambda x:x[2])
uf = UnionFind(n)
max_edge = -1
e_idx = 0
while uf.cot>1 and e_idx<len(edges):
u,v,w = edges[e_idx]
if uf.union(u,v):
max_edge = w
e_idx += 1
cot = 0
for e in mj:
if e>=max_edge:
cot+=1
print(cot)
if __name__=='__main__':
main()