PAST1L

https://gyazo.com/622d3e70835a1497220daa46d7958222

Thoughts.

Connect 30 vertices at the lowest cost

There are five auxiliary vertices that may or may not be connected.

That's nasty.

Find the minimum global tree with respect to "whether to pick 5 vertices" of 2^5?

Maybe we could start with the larger ones since removing the vertices won't improve the cost, but we'll get there in time without having to do that.

Official Explanation

35 vertices and about 10^3 edges, so there's plenty of time to search for all 2^5 patterns.

1WA

code:python

def solve(N, M, LARGE, SMALL):

from math import sqrt

edges = []

for i in range(N):

for j in range(i + 1, N):

d = sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

if c1 != c2:

d *= 10

edges.append((d, i, j))

INF = 9223372036854775807

ret = INF

for subset in range(2 ** M):

for m in range(M):

if subset & (1 << m):

for i in range(N):

d = sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

if c1 != c2:

d *= 10

edges.append((d, i, N + m))

init_unionfind(N + M)

edges.sort()

cost = 0

for d, i, j in edges:

if is_connected(i, j):

continue

unite(i, j)

cost += d

ret = min(ret, cost)

return ret

---