結果

問題 No.168 ものさし
ユーザー roaris
提出日時 2019-10-30 15:40:13
言語 PyPy3
(7.0.0)
結果
AC  
実行時間 1,510 ms
コード長 1,515 Byte
コンパイル時間 254 ms
使用メモリ 159,732 KB
最終ジャッジ日時 2019-10-30 15:40:29

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 485 ms
100,396 KB
challenge01.txt AC 244 ms
78,628 KB
challenge02.txt AC 242 ms
79,736 KB
sample1.txt AC 238 ms
78,916 KB
sample2.txt AC 248 ms
79,220 KB
sample3.txt AC 268 ms
79,852 KB
sample4.txt AC 242 ms
78,632 KB
test1.txt AC 240 ms
78,620 KB
test2.txt AC 239 ms
78,636 KB
test3.txt AC 259 ms
78,864 KB
test4.txt AC 289 ms
81,320 KB
test5.txt AC 434 ms
97,656 KB
test6.txt AC 1,002 ms
136,196 KB
test7.txt AC 1,406 ms
158,644 KB
test8.txt AC 1,363 ms
159,532 KB
test9.txt AC 251 ms
78,908 KB
test10.txt AC 247 ms
79,380 KB
test11.txt AC 256 ms
81,232 KB
test12.txt AC 320 ms
82,400 KB
test13.txt AC 1,391 ms
159,732 KB
test14.txt AC 1,510 ms
158,568 KB
test15.txt AC 1,452 ms
159,440 KB
test16.txt AC 1,451 ms
159,096 KB
テストケース一括ダウンロード

ソースコード

diff # 
import sys
input = sys.stdin.readline
from decimal import *

class Unionfind():
    def __init__(self, n):
        self.par = [-1] * n
        self.rank = [1] * n
    
    def root(self, x):
        if self.par[x] < 0:
            return x
        
        self.par[x] = self.root(self.par[x])
        
        return self.par[x]
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        
        if rx != ry:
            if self.rank[rx] >= self.rank[ry]:
                self.par[rx] += self.par[ry]
                self.par[ry] = rx
                
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] += 1
            else:
                self.par[ry] += self.par[rx]
                self.par[rx] = ry
    
    def is_same(self, x, y):
        return self.root(x) == self.root(y)
    
    def count(self, x):
        return -self.par[x]
    
N = int(input())
XY = [tuple(map(int, input().split())) for _ in range(N)]
edges = []

for i in range(N):
    for j in range(i+1, N):
        Xi, Yi = XY[i]
        Xj, Yj = XY[j]
        edges.append((i, j, (Xi-Xj)**2+(Yi-Yj)**2))

edges.sort(key=lambda k: k[2])
uf = Unionfind(N)

for s, t, w in edges:
    uf.unite(s, t)
    
    if uf.is_same(0, N-1):
        ng, ok = -1, 10**11
        
        while abs(ok-ng) > 1:
            mid = (ng+ok)//2
            
            if (mid*10)**2 >= w:
                ok = mid
            else:
                ng = mid
        
        print(10*ok)
        break
0