結果
問題 | No.2179 Planet Traveler |
ユーザー | Hydru |
提出日時 | 2023-01-06 23:55:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 332 ms / 3,000 ms |
コード長 | 1,284 bytes |
コンパイル時間 | 360 ms |
コンパイル使用メモリ | 82,384 KB |
実行使用メモリ | 156,992 KB |
最終ジャッジ日時 | 2024-05-07 23:56:29 |
合計ジャッジ時間 | 6,747 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
54,704 KB |
testcase_01 | AC | 42 ms
54,880 KB |
testcase_02 | AC | 41 ms
55,356 KB |
testcase_03 | AC | 40 ms
55,080 KB |
testcase_04 | AC | 40 ms
56,188 KB |
testcase_05 | AC | 41 ms
54,292 KB |
testcase_06 | AC | 41 ms
55,452 KB |
testcase_07 | AC | 44 ms
59,620 KB |
testcase_08 | AC | 48 ms
63,088 KB |
testcase_09 | AC | 54 ms
64,848 KB |
testcase_10 | AC | 49 ms
62,404 KB |
testcase_11 | AC | 178 ms
113,760 KB |
testcase_12 | AC | 232 ms
107,156 KB |
testcase_13 | AC | 286 ms
129,388 KB |
testcase_14 | AC | 248 ms
156,992 KB |
testcase_15 | AC | 255 ms
156,692 KB |
testcase_16 | AC | 264 ms
156,768 KB |
testcase_17 | AC | 293 ms
121,404 KB |
testcase_18 | AC | 332 ms
121,480 KB |
testcase_19 | AC | 286 ms
122,188 KB |
testcase_20 | AC | 94 ms
84,496 KB |
testcase_21 | AC | 298 ms
120,652 KB |
testcase_22 | AC | 204 ms
99,876 KB |
testcase_23 | AC | 187 ms
95,580 KB |
testcase_24 | AC | 259 ms
113,388 KB |
testcase_25 | AC | 201 ms
105,124 KB |
testcase_26 | AC | 259 ms
114,292 KB |
testcase_27 | AC | 101 ms
84,756 KB |
testcase_28 | AC | 164 ms
92,368 KB |
testcase_29 | AC | 259 ms
110,652 KB |
ソースコード
from math import sqrt from collections import deque n=int(input()) Z=[list(map(int,input().split())) for _ in range(n)] G=[[0 for _ in range(n)] for _ in range(n)] dist=[0] dist_set=set([0]) def max_sqrt(a): l=1 r=int(sqrt(a)+1) while(r-l>1): mid=(r+l)//2 if(mid**2<=a): l=mid else: r=mid return l for i in range(n-1): for j in range(i+1,n): if i==j: continue if Z[i][2]==Z[j][2]: d=(Z[i][0]-Z[j][0])**2+(Z[i][1]-Z[j][1])**2 else: d1=Z[i][0]**2+Z[i][1]**2 d2=Z[j][0]**2+Z[j][1]**2 d=d1+d2-max_sqrt(4*d1*d2) G[i][j]=d G[j][i]=d if d not in dist_set: dist.append(d) dist_set.add(d) def dfs(G,d): not_visit=set([i for i in range(1,n)]) Q=deque() Q.append(0) while(Q): v=Q.pop() visit=set() for i in not_visit: if G[v][i]<=d: visit.add(i) Q.append(i) if i==n-1: return True not_visit-=visit return False dist.sort() l=-1 r=len(dist)-1 while(r-l>1): mid=(r+l)//2 if(dfs(G,dist[mid])): r=mid else: l=mid print(dist[r])