結果

問題 No.1639 最小通信路
ユーザー wolgnikwolgnik
提出日時 2021-08-06 22:01:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,233 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 81,644 KB
実行使用メモリ 245,976 KB
最終ジャッジ日時 2024-09-17 01:59:49
合計ジャッジ時間 23,637 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
54,524 KB
testcase_01 AC 110 ms
76,684 KB
testcase_02 AC 1,962 ms
245,976 KB
testcase_03 AC 515 ms
81,096 KB
testcase_04 WA -
testcase_05 AC 537 ms
88,224 KB
testcase_06 AC 871 ms
109,244 KB
testcase_07 AC 149 ms
77,700 KB
testcase_08 AC 1,451 ms
170,664 KB
testcase_09 WA -
testcase_10 AC 377 ms
81,280 KB
testcase_11 AC 1,051 ms
122,808 KB
testcase_12 AC 457 ms
83,588 KB
testcase_13 AC 1,953 ms
234,612 KB
testcase_14 WA -
testcase_15 AC 411 ms
82,500 KB
testcase_16 AC 1,090 ms
132,844 KB
testcase_17 AC 1,444 ms
168,984 KB
testcase_18 AC 222 ms
77,528 KB
testcase_19 AC 629 ms
92,672 KB
testcase_20 AC 1,456 ms
176,092 KB
testcase_21 WA -
testcase_22 AC 488 ms
85,540 KB
testcase_23 AC 819 ms
106,236 KB
testcase_24 AC 427 ms
84,148 KB
testcase_25 AC 175 ms
77,408 KB
testcase_26 AC 160 ms
77,596 KB
testcase_27 WA -
testcase_28 AC 122 ms
77,184 KB
testcase_29 AC 254 ms
78,600 KB
testcase_30 AC 346 ms
79,596 KB
testcase_31 AC 173 ms
77,212 KB
testcase_32 AC 290 ms
79,088 KB
testcase_33 AC 160 ms
76,856 KB
testcase_34 AC 288 ms
79,160 KB
testcase_35 AC 515 ms
81,288 KB
testcase_36 AC 348 ms
78,728 KB
testcase_37 AC 304 ms
79,704 KB
testcase_38 WA -
testcase_39 AC 177 ms
77,392 KB
testcase_40 AC 147 ms
77,056 KB
testcase_41 AC 156 ms
76,840 KB
testcase_42 AC 347 ms
79,832 KB
testcase_43 AC 163 ms
77,212 KB
testcase_44 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
N = int(input())
e = [[] for _ in range(N + 1)]
for _ in range(N * (N - 1) // 2):
  u, v, c = map(int, input().split())
  e[u].append((v, c, 0))
  e[v].append((u, c, 0))

import heapq
class prim:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def MSTcost(self):
    h = []
    visited = [0] * (self.n + 1)
    b = pow(10, 6)
    for edge in e[1]:
      heapq.heappush(h, edge[1] * b ** 2 + edge[0] * b + edge[2])
    res = 0
    reslist = []
    visited[1] = 1
    while len(h):
      p = heapq.heappop(h)
      p01 = p // b
      p2 = p % b
      p0 = p01 // b
      p1 = p01 % b
      if visited[p1]: continue
      visited[p1] = 1
      for q in self.e[p1]:
        if visited[q[0]]:
          continue
        heapq.heappush(h, q[1] * b ** 2 + q[0] * b + q[2])
      res += p0
      reslist.append(p2)
    return res, reslist

pri = prim(N, e)
cost = pri.MSTcost()[0]

ok = 10 ** 100
ng = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  me = [[] for _ in range(N + 1)]
  for x in range(1, N + 1):
    for y, c, _ in e[x]:
      if c <= m: me[x].append((y, c, 0))
  pri = prim(N, me)
  mst = pri.MSTcost()
  if mst[0] == cost and len(mst[1]) == N - 1: ok = m
  else: ng = m
print(ok)
0