結果

問題 No.2354 Poor Sight in Winter
ユーザー navel_tosnavel_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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 48 ms
55,424 KB
testcase_01 AC 49 ms
55,040 KB
testcase_02 AC 50 ms
55,800 KB
testcase_03 AC 45 ms
55,168 KB
testcase_04 AC 46 ms
55,040 KB
testcase_05 AC 45 ms
54,912 KB
testcase_06 AC 48 ms
55,296 KB
testcase_07 AC 48 ms
55,296 KB
testcase_08 AC 50 ms
55,680 KB
testcase_09 AC 59 ms
66,884 KB
testcase_10 AC 70 ms
70,196 KB
testcase_11 AC 983 ms
83,328 KB
testcase_12 AC 1,333 ms
80,640 KB
testcase_13 AC 870 ms
80,640 KB
testcase_14 AC 953 ms
83,188 KB
testcase_15 AC 948 ms
86,364 KB
testcase_16 AC 960 ms
83,584 KB
testcase_17 AC 931 ms
82,432 KB
testcase_18 AC 420 ms
79,660 KB
testcase_19 AC 707 ms
81,620 KB
testcase_20 AC 486 ms
81,128 KB
testcase_21 AC 189 ms
78,496 KB
testcase_22 AC 348 ms
79,104 KB
testcase_23 AC 341 ms
79,800 KB
testcase_24 AC 657 ms
82,400 KB
testcase_25 AC 263 ms
78,924 KB
testcase_26 AC 249 ms
78,552 KB
testcase_27 AC 134 ms
77,312 KB
testcase_28 AC 178 ms
78,448 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