結果

問題 No.2354 Poor Sight in Winter
ユーザー navel_tosnavel_tos
提出日時 2023-06-16 23:17:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,308 ms / 2,000 ms
コード長 2,602 bytes
コンパイル時間 323 ms
コンパイル使用メモリ 87,052 KB
実行使用メモリ 89,340 KB
最終ジャッジ日時 2023-09-06 22:14:55
合計ジャッジ時間 14,151 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 97 ms
71,508 KB
testcase_01 AC 93 ms
71,540 KB
testcase_02 AC 96 ms
72,308 KB
testcase_03 AC 92 ms
71,548 KB
testcase_04 AC 93 ms
71,676 KB
testcase_05 AC 96 ms
71,512 KB
testcase_06 AC 95 ms
71,856 KB
testcase_07 AC 96 ms
71,816 KB
testcase_08 AC 96 ms
71,608 KB
testcase_09 AC 110 ms
77,364 KB
testcase_10 AC 121 ms
77,332 KB
testcase_11 AC 1,048 ms
88,164 KB
testcase_12 AC 1,308 ms
82,292 KB
testcase_13 AC 896 ms
82,384 KB
testcase_14 AC 1,008 ms
85,348 KB
testcase_15 AC 957 ms
89,340 KB
testcase_16 AC 983 ms
85,372 KB
testcase_17 AC 969 ms
84,516 KB
testcase_18 AC 465 ms
81,244 KB
testcase_19 AC 746 ms
83,876 KB
testcase_20 AC 526 ms
82,892 KB
testcase_21 AC 220 ms
80,172 KB
testcase_22 AC 385 ms
80,820 KB
testcase_23 AC 396 ms
81,000 KB
testcase_24 AC 697 ms
84,504 KB
testcase_25 AC 302 ms
80,252 KB
testcase_26 AC 274 ms
80,780 KB
testcase_27 AC 163 ms
79,104 KB
testcase_28 AC 212 ms
80,276 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder393E

'''
Dがあまりに通らなくて悲しくなったのでEへ。
視界で二分探索したい欲望をぐっと抑える。むりですか？むりですね

こっちでMSTでは。

ああ理解した。難しいわこれ。
'''
#UnionFind
class UnionFind:
    def __init__(self,N): self._parent=[-1 for i in[0]*N]
    def find(self,v):  #頂点vの親を探し、経路圧縮する
        vertices=[]
        while self._parent[v]>=0: vertices.append(v);v=self._parent[v]
        for i in vertices: self._parent[i]=v
        return v
    def unite(self,x,y):  #頂点xとyを併合し、併合の有無を返す
        x,y = self.find(x),self.find(y)
        if x==y: return 0
        if self._parent[x]>self._parent[y]: x,y=y,x  #負値で管理
        self._parent[x]+=self._parent[y]; self._parent[y]=x; return 1
    def same(self,x,y):return self.find(x)==self.find(y)   #xとyは同一集合か返す
    def size(self,x):  return -self._parent[self.find(x)]  #xの集合のサイズを求める

import heapq as hq
from collections import defaultdict as dd
f=lambda:tuple(map(int,input().split()))

N,K=f(); p,q,r,s=f(); P=[(p,q)]+[f() for _ in range(N)]+[(r,s)]
dist=[[abs(P[i][0]-P[j][0])+abs(P[i][1]-P[j][1]) for j in range(N+2)] for i in range(N+2)]
OK,NG=10**11,0; 
while abs(OK-NG)>1:
    mid=(OK+NG)//2; UF=UnionFind(N+2)
    #明かりを使わない場合の集合状態を管理する
    for i in range(N+2):
        for j in range(i+1,N+2):
            if dist[i][j]<=mid: UF.unite(i,j)
    #すべての親番号を取得 ついでに集合全体の大きさも確認
    parent=[UF.find(i) for i in range(N+2)]; D=set()
    if parent[0]==parent[-1]: OK=mid; continue
    for now in parent: D.add(now)
    D=sorted(D); E={j:i for i,j in enumerate(D)}; parent=[E[i] for i in parent]

    #集合間最短距離を管理
    size=len(D); cost=[[10**18]*size for _ in range(size)]
    for i in range(N+2):
        for j in range(N+2):
            cost[parent[i]][parent[j]]=min(cost[parent[i]][parent[j]],dist[i][j])

    #ダイクストラ法 (本数、現在地)
    Q=[(0,parent[0])]; visited=[10**18]*size
    while Q:
        c,now=hq.heappop(Q)
        if visited[now]<c: continue
        if c>K: continue
        visited[now]=c
        if now==parent[-1]: break
        for next in range(size):
            if next==now: continue
            need=-(-cost[now][next]//mid)-1
            if c+need>=visited[next]: continue
            visited[next]=c+need; hq.heappush(Q,(c+need,next))
    OK,NG=(mid,NG) if visited[parent[-1]]<=K else (OK,mid)
print(OK)
0