結果
問題 | No.2179 Planet Traveler |
ユーザー |
|
提出日時 | 2023-01-20 11:31:42 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,079 bytes |
コンパイル時間 | 223 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 83,328 KB |
最終ジャッジ日時 | 2024-06-23 02:05:12 |
合計ジャッジ時間 | 8,436 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 17 WA * 9 |
ソースコード
from collections import *from itertools import *from functools import *from heapq import *import math,sysinput = sys.stdin.readlineN = int(input())dist = [[0]*N for _ in range(N)]XYT = [tuple(map(int,input().split())) for _ in range(N)]for i in range(N-1):xi,yi,ti = XYT[i]for j in range(i+1,N):xj,yj,tj = XYT[j]if ti==tj:td = (xi-xj)**2 + (yi-yj)**2else:td = xi**2+yi**2+xj**2+yj**2-2*math.floor((math.sqrt(xi**2+yi**2)*math.sqrt(xj**2+yj**2)))dist[i][j]=tddist[j][i]=tdclass DSU:def __init__(self, n):self._n = nself.parent_or_size = [-1] * ndef merge(self, a, b):assert 0 <= a < self._nassert 0 <= b < self._nx, y = self.leader(a), self.leader(b)if x == y: return xif -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, xself.parent_or_size[x] += self.parent_or_size[y]self.parent_or_size[y] = xreturn xdef same(self, a, b):assert 0 <= a < self._nassert 0 <= b < self._nreturn self.leader(a) == self.leader(b)def leader(self, a):assert 0 <= a < self._nif self.parent_or_size[a] < 0: return aself.parent_or_size[a] = self.leader(self.parent_or_size[a])return self.parent_or_size[a]def size(self, a):assert 0 <= a < self._nreturn -self.parent_or_size[self.leader(a)]def groups(self):leader_buf = [self.leader(i) for i in range(self._n)]result = [[] for _ in range(self._n)]for i in range(self._n): result[leader_buf[i]].append(i)return [r for r in result if r != []]def is_ok(s):D = DSU(N)for i in range(N-1):for j in range(i+1,N):if dist[i][j]<=s:D.merge(i,j)return D.same(0,N-1)x = -1y = 10**18while y-x>1:mid = (y+x)//2if is_ok(mid):y = midelse:x = midprint(y)