結果
問題 | No.168 ものさし |
ユーザー | convexineq |
提出日時 | 2020-12-13 13:13:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 986 bytes |
コンパイル時間 | 1,014 ms |
コンパイル使用メモリ | 81,616 KB |
実行使用メモリ | 83,864 KB |
最終ジャッジ日時 | 2023-10-20 03:40:37 |
合計ジャッジ時間 | 2,772 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 70 ms
70,456 KB |
testcase_01 | AC | 34 ms
53,616 KB |
testcase_02 | AC | 40 ms
53,616 KB |
testcase_03 | AC | 35 ms
53,616 KB |
testcase_04 | AC | 35 ms
53,616 KB |
testcase_05 | AC | 37 ms
53,616 KB |
testcase_06 | AC | 35 ms
53,616 KB |
testcase_07 | AC | 37 ms
53,616 KB |
testcase_08 | AC | 34 ms
53,616 KB |
testcase_09 | AC | 50 ms
64,260 KB |
testcase_10 | AC | 52 ms
64,024 KB |
testcase_11 | AC | 68 ms
70,460 KB |
testcase_12 | AC | 83 ms
81,312 KB |
testcase_13 | AC | 96 ms
83,864 KB |
testcase_14 | AC | 81 ms
83,520 KB |
testcase_15 | AC | 36 ms
53,624 KB |
testcase_16 | AC | 48 ms
61,940 KB |
testcase_17 | AC | 50 ms
64,028 KB |
testcase_18 | AC | 51 ms
64,016 KB |
testcase_19 | AC | 88 ms
83,660 KB |
testcase_20 | AC | 84 ms
83,624 KB |
testcase_21 | AC | 96 ms
83,804 KB |
testcase_22 | AC | 90 ms
83,796 KB |
ソースコード
def Prim_dense(g): n = len(g) INF = 2*10**18 + 5 smallest = [INF]*n # 頂点 i から到達できる使用済みの点までの距離の最小値 smallest[0] = 0 used = [0]*n ans = 0 for i in range(n): v = -1 d = INF for j in range(n): if used[j]==0 and smallest[j] < d: v = j d = smallest[j] ans = max(ans,d) if v==-1: #非連結 return None break if v==n-1: return ans used[v] = 1 for j in range(n): if used[j]==0 and smallest[j] > g[v][j]: smallest[j] = g[v][j] #return sum(smallest) return smallest[-1] n = int(input()) xy = [list(map(int,input().split())) for _ in range(n)] g = [[(xi-xj)**2+(yi-yj)**2 for xj,yj in xy] for xi,yi in xy] d = Prim_dense(g) r = int(d**0.5) v = max(0,(r-3)//10*10) for i in range(v,v+100,10): if i*i >= d: print(i) break