結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー titan23
提出日時 2022-07-30 16:01:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 946 ms / 1,000 ms
コード長 3,747 bytes
コンパイル時間 249 ms
実行使用メモリ 144,032 KB
スコア 2,379,200
最終ジャッジ日時 2022-07-30 16:02:01
合計ジャッジ時間 31,095 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import time
import random
import math
input = lambda: sys.stdin.readline().rstrip()

from collections import defaultdict
class UnionFind:

  def __init__(self, n: int):
    "Build a new UnionFind. / O(N)"
    self.__n = n
    self.__group_numbers = n
    self.__parents = [-1] * n

  def __find(self, x: int) -> int:
    a = x
    while self.__parents[a] >= 0:
      a = self.__parents[a]
    while self.__parents[x] >= 0:
      self.__parents[x] = a
      x = self.__parents[x]
    return a

  def unite(self, x: int, y: int) -> None:
    "Untie x and y. / O(α(N))"
    x, y = self.__find(x), self.__find(y)
    if x == y:
      return
    self.__group_numbers -= 1
    if self.__parents[x] > self.__parents[y]:
      x, y = y, x
    self.__parents[x] += self.__parents[y]
    self.__parents[y] = x

  def size(self, x: int) -> int:
    "xが属する集合の要素数. / O(α(N))"
    return -self.__parents[self.__find(x)]

  def same(self, x: int, y: int) -> bool:
    "Return True if 'same' else False. / O(α(N))"
    return self.__find(x) == self.__find(y)

  def roots(self) -> list:
    "Return all roots. / O(N)"
    return [i for i,x in enumerate(self.__parents) if x < 0]

  def group_count(self) -> int:
    "Return the number of groups. / O(1)"
    return self.__group_numbers

  def all_group_members(self) -> list:
    "Return all_group_members. / O(Nα(N))"
    group_members = defaultdict(list)
    for member in range(self.__n):
      group_members[self.__find(member)].append(member)
    return group_members

  def relax(self) -> None:
    "/relax."
    for i in range(self.__n):
      self.__find(i)

  def __str__(self) -> str:
    ret = '<UnionFind> [\n'
    ret += '\n'.join(f'  {k}: {v}' for k,v in self.all_group_members().items())
    ret += '\n]\n'
    return ret


#  -----------------------  #

n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
ab_set = set(ab)
ALP = 5
LIMIT = 0.8
START = time.time()
 
def MST(E):
  uf = UnionFind(n+m+1)
  E.sort(key=lambda x: -x[2])
  used = []
  cost = 0
  for i,j,c in E:
    if uf.same(i, j):
      continue
    uf.unite(i, j)
    used.append((i, j))
    cost += c
  return cost, used

def make_stations():
  stations = []
  while len(stations) < m:
    i, j = random.randint(0, 1000), random.randint(0, 1000)
    if (i, j) in ab_set:
      continue
    stations.append((i, j))

  E = []
  for i in range(n+m):
    for j in range(n+m):
      if i == j:
        continue
      cost = 0
      if i < n:
        if j < n:
          cost = ALP * ALP * ((ab[i][0] - ab[j][0])**2 + (ab[i][1] - ab[j][1])**2)
        else:
          cost = ALP * ((ab[i][0] - stations[j-n][0])**2 + (ab[i][1] - stations[j-n][1])**2)
      else:
        if j < n:
          cost = ALP * ((stations[i-n][0] - ab[j][0])**2 + (stations[i-n][1] - ab[j][1])**2)
        else:
          cost = ((stations[i-n][0] - stations[j-n][0])**2 + (stations[i-n][1] - stations[j-n][1])**2)
      E.append((i+1, j+1, cost))
  score, mst = MST(E)
  return stations, score, mst

from collections import deque
def make_root(mst):
  G = [[] for _ in range(n+m+1)]
  for i,j in mst:
    G[i].append(j)
    G[j].append(i)
  ret = []
  seen = set([1])
  todo = deque([1])
  while todo:
    v = todo.popleft()
    ret.append(v)
    for x in G[v]:
      if x in seen: continue
      todo.append(x)
      seen.add(x)
  return ret

vestscore = float('inf')
ans = []
while time.time() - START < LIMIT:
  stations, score, mst = make_stations()
  if score < vestscore:
    vestscore = score
    ans = [stations[:], mst[:]]
root = make_root(ans[1])
for i in ans[0]:
  print(*i)
print(len(root)+1)
for i in root:
  if i <= n:
    print(1, i)
  else:
    print(2, i-n)
print(1, 1)
0