結果

問題 No.2354 Poor Sight in Winter
ユーザー navel_tos
提出日時 2023-06-16 23:17:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,333 ms / 2,000 ms
コード長 2,602 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 86,364 KB
最終ジャッジ日時 2024-06-24 16:25:29
合計ジャッジ時間 13,248 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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