結果

問題 No.168 ものさし
ユーザー roaris
提出日時 2019-10-30 15:07:22
言語 PyPy3
(7.0.0)
結果
TLE  
実行時間 -
コード長 1,508 Byte
コンパイル時間 2,015 ms
使用メモリ 132,740 KB
最終ジャッジ日時 2019-10-30 15:07:35

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 1,797 ms
87,964 KB
challenge01.txt AC 102 ms
67,328 KB
challenge02.txt AC 101 ms
67,960 KB
sample1.txt AC 103 ms
67,328 KB
sample2.txt AC 110 ms
67,756 KB
sample3.txt AC 105 ms
67,344 KB
sample4.txt AC 108 ms
67,848 KB
test1.txt AC 101 ms
67,488 KB
test2.txt AC 110 ms
68,508 KB
test3.txt AC 227 ms
70,032 KB
test4.txt AC 352 ms
71,772 KB
test5.txt AC 1,770 ms
85,652 KB
test6.txt TLE -
test7.txt -- -
test8.txt -- -
test9.txt -- -
test10.txt -- -
test11.txt -- -
test12.txt -- -
test13.txt -- -
test14.txt -- -
test15.txt -- -
test16.txt -- -
テストケース一括ダウンロード

ソースコード

diff #
import sys
input = sys.stdin.readline

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]

def isOk(x):
    uf = Unionfind(N)
    
    for s, t, w in square_edges:
        if w <= (10*x)**2:
            uf.unite(s, t)
        else:
            break
    
    return uf.is_same(0, N-1)
    
N = int(input())
XY = [tuple(map(int, input().split())) for _ in range(N)]
square_edges = []

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

square_edges.sort(key=lambda k: k[2])
ng, ok = -1, 10**11

while abs(ok-ng) > 1:
    mid = (ng+ok)//2
    
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(10*ok)
0