3306 | 2023. 02. 24 19:31:33 | 12Boti | Hírvivők csoportosítása (40) | python3 | Elfogadva 40/40 | 218ms | 41344 KiB |
N, M, H, K = map(int, input().split())
hs = [tuple(map(int, input().split())) for _ in range(H)]
# counting sort of edges, we can afford O(n^2)
edges = [[] for _ in range(20000)]
for i in range(H):
for j in range(i + 1, H):
dist = abs(hs[i][0] - hs[j][0]) + abs(hs[i][1] - hs[j][1])
edges[dist].append((i, j))
# https://en.wikipedia.org/wiki/Disjoint-set_data_structure
par = list(range(H))
rank = [0] * H
count = H
def find(a):
while par[a] != a:
# path halving
par[a] = par[par[a]]
a = par[a]
return a
def union(a, b):
global count
a = find(a)
b = find(b)
if a == b:
return
count -= 1
# merge by rank
if rank[a] == rank[b]:
par[b] = a
rank[a] += 1
elif rank[a] > rank[b]:
par[b] = a
else:
par[a] = b
for dist, es in enumerate(edges):
for a, b in es:
union(a, b)
if count <= K:
print(dist)
exit()
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 40/40 | ||||||
1 | Elfogadva | 0/0 | 26ms | 14400 KiB | |||
2 | Elfogadva | 0/0 | 142ms | 34360 KiB | |||
3 | Elfogadva | 1/1 | 29ms | 15996 KiB | |||
4 | Elfogadva | 1/1 | 26ms | 15428 KiB | |||
5 | Elfogadva | 1/1 | 46ms | 18592 KiB | |||
6 | Elfogadva | 1/1 | 45ms | 18812 KiB | |||
7 | Elfogadva | 1/1 | 32ms | 16648 KiB | |||
8 | Elfogadva | 1/1 | 29ms | 16816 KiB | |||
9 | Elfogadva | 1/1 | 30ms | 16720 KiB | |||
10 | Elfogadva | 1/1 | 46ms | 19088 KiB | |||
11 | Elfogadva | 1/1 | 45ms | 19300 KiB | |||
12 | Elfogadva | 1/1 | 46ms | 19348 KiB | |||
13 | Elfogadva | 3/3 | 202ms | 40168 KiB | |||
14 | Elfogadva | 3/3 | 210ms | 40152 KiB | |||
15 | Elfogadva | 3/3 | 201ms | 40284 KiB | |||
16 | Elfogadva | 3/3 | 195ms | 40488 KiB | |||
17 | Elfogadva | 3/3 | 200ms | 40428 KiB | |||
18 | Elfogadva | 3/3 | 194ms | 40704 KiB | |||
19 | Elfogadva | 3/3 | 218ms | 40956 KiB | |||
20 | Elfogadva | 3/3 | 206ms | 41212 KiB | |||
21 | Elfogadva | 3/3 | 196ms | 41344 KiB | |||
22 | Elfogadva | 3/3 | 194ms | 41124 KiB |