結果
問題 | No.2179 Planet Traveler |
ユーザー |
|
提出日時 | 2023-01-06 23:12:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 791 ms / 3,000 ms |
コード長 | 2,329 bytes |
コンパイル時間 | 146 ms |
コンパイル使用メモリ | 82,112 KB |
実行使用メモリ | 78,840 KB |
最終ジャッジ日時 | 2024-11-30 19:57:27 |
合計ジャッジ時間 | 11,875 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
import sysinput = lambda :sys.stdin.readline()[:-1]ni = lambda :int(input())na = lambda :list(map(int,input().split()))yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")#######################################################################from collections import defaultdictclass UnionFind():def __init__(self, n):self.n = nself.parents = [-1] * ndef find(self, x):if self.parents[x] < 0:return xelse:self.parents[x] = self.find(self.parents[x])return self.parents[x]def union(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 size(self, x):return -self.parents[self.find(x)]def same(self, x, y):return self.find(x) == self.find(y)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 group_count(self):return len(self.roots())def all_group_members(self):group_members = defaultdict(list)for member in range(self.n):group_members[self.find(member)].append(member)return group_membersdef __str__(self):return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())n = ni()x,y,t = zip(*[na() for i in range(n)])ok = 10**10ng = -1while ok - ng > 1:d = ok+ng>>1uf = UnionFind(n)for i in range(n):for j in range(i+1, n):if t[i] == t[j]:if (x[i]-x[j])**2+(y[i]-y[j])**2 <= d:uf.union(i, j)else:d1, d2 = min(x[i]**2+y[i]**2,x[j]**2+y[j]**2),max(x[i]**2+y[i]**2,x[j]**2+y[j]**2)#print(d1,d2)if (d1 + d2 - d)**2 <= 4 * d1 *d2 or d1 + d2 - d <= 0:uf.union(i, j)#print(d, uf.all_group_members())if uf.same(0, n-1):ok = delse:ng = dprint(ok)