結果
問題 | No.2179 Planet Traveler |
ユーザー |
![]() |
提出日時 | 2022-08-02 21:49:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 597 ms / 3,000 ms |
コード長 | 1,474 bytes |
コンパイル時間 | 146 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 128,384 KB |
最終ジャッジ日時 | 2024-11-30 16:26:45 |
合計ジャッジ時間 | 10,287 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
import sys, mathinput = sys.stdin.readlineclass UnionFind():def __init__(self, n):self.n = nself.parents = [-1] * ndef find(self, x):if(self.parents[x] < 0):return xself.parents[x] = self.find(self.parents[x])return self.parents[x]def unite(self, x, y):x = self.find(x)y = self.find(y)if(x == y):returnif(self.parents[x] > self.parents[y]):x, y = y, xself.parents[x] += self.parents[y]self.parents[y] = xdef same(self, x, y):return self.find(x) == self.find(y)def size(self, x):return -self.parents[self.find(x)]def members(self, x):root = self.find(x)return [i for i in range(self.n) if self.find(i) == root]def roots(self):return [i for i, x in enumerate(self.parents) if x < 0]def isqrt(n):rn = math.sqrt(n)ok = int(rn - 2)ng = int(rn + 2)while(ng - ok > 1):k = (ok + ng) >> 1if(k * k <= n):ok = kelse:ng = kreturn ok"""Main Code"""n = int(input())planet = [list(map(int, input().split())) for _ in [0] * n]edge = []for i in range(0, n-1):for j in range(i+1, n):p1 = planet[i]p2 = planet[j]d = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2if(p1[2] != p2[2]):r1 = p1[0] ** 2 + p1[1] ** 2r2 = p2[0] ** 2 + p2[1] ** 2d = r1 + r2 - isqrt(4 * r1 * r2)edge.append((i, j, d))edge.sort(key = lambda x : x[2])uni = UnionFind(n)ans = 0for a, b, c in edge:ans = cuni.unite(a, b)if(uni.same(0, n-1)):breakprint(ans)