結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 1,780 ms
99,872 KB
challenge01.txt AC 108 ms
78,300 KB
challenge02.txt AC 104 ms
78,444 KB
sample1.txt AC 104 ms
78,460 KB
sample2.txt AC 100 ms
78,428 KB
sample3.txt AC 100 ms
78,404 KB
sample4.txt AC 108 ms
79,204 KB
test1.txt AC 100 ms
78,296 KB
test2.txt AC 100 ms
78,500 KB
test3.txt AC 212 ms
80,484 KB
test4.txt AC 356 ms
82,476 KB
test5.txt AC 1,824 ms
96,604 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