結果

問題 No.2696 Sign Creation
コンテスト
ユーザー navel_tos
提出日時 2024-03-22 22:02:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 710 ms / 2,500 ms
コード長 3,513 bytes
コンパイル時間 240 ms
コンパイル使用メモリ 82,436 KB
実行使用メモリ 253,104 KB
最終ジャッジ日時 2024-12-20 11:58:14
合計ジャッジ時間 8,962 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#yukicoder423E Sign Creation

#UnionFind(Rollback可能 経路圧縮はできません)
class Rollback_UF:
    def __init__(self,N:int): self._parent=[-1 for i in[0]*N]; self._history=[]
    def find(self,v:int):  #親を探す 経路圧縮は行わない
        while self._parent[v]>=0: v=self._parent[v]
        return v
    def unite(self,x:int,y:int):  #頂点xとyを併合する
        x,y=self.find(x),self.find(y)
        x,y=(x,y) if self._parent[x]<=self._parent[y] else (y,x)  #要素数の大きい集合をxに
        if x==y: self._history.append((x,-1,-1,-1)); return 0
        self._history.append((x,y,self._parent[x],self._parent[y]))
        self._parent[x]+=self._parent[y]; self._parent[y]=x; return 1
        
    def same(self,x:int,y:int):return self.find(x)==self.find(y)   #xとyは同一集合か返す
    def size(self,x:int):  return -self._parent[self.find(x)]  #xの集合のサイズを求める
    def rollback(self):  #1回分roll backする
        if not self._history: return 0
        x,y,sx,sy=self._history.pop()
        if y == -1: return 0  #同一要素のuniteは無効
        self._parent[x],self._parent[y]=sx,sy; return 1


#入力受取
H, W, N, D = map(int, input().split())
G = [[-1] * W for _ in range(H)]
T = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
for i, (h, w) in enumerate(T):
    assert G[h][w] == -1
    G[h][w] = i

#距離1以上D以内の頂点を列挙
dist = lambda x1, y1, x2, y2: abs(x1 - x2) + abs(y1 - y2)
D = [(h, w) for h in range(- D, D + 1) for w in range(- D, D + 1)
     if 1 <= abs(h) + abs(w) <= D]

#UnionFind
grid = lambda h, w: h * W + w
visited = [[False] * W for _ in range(H)]
UF = Rollback_UF(H * W)
for h in range(H):
    for w in range(W):
        if G[h][w] == -1: continue
        if visited[h][w]: continue
        Q = [(h, w)]
        i = grid(h, w)
        while Q:
            x, y = Q.pop()
            if visited[x][y] == True:
                continue
            visited[x][y] = True
            j = grid(x, y)
            UF.unite(i, j)
            
            for p, q in D:
                u, v = x + p, y + q
                if u in range(0, H) and v in range(0, W):
                    if G[u][v] != -1 and visited[u][v] == False:
                        Q.append((u, v))

for h in range(H):
    for w in range(W):
        if G[h][w] != -1:
            assert visited[h][w]
        else:
            assert visited[h][w] == False

#現在の星座数を数え上げ
cnt = sum(1 for h in range(H) for w in range(W)
          if G[h][w] != -1 and grid(h, w) == UF.find(grid(h, w)) and
          UF.size(grid(h, w)) > 1)
Lt = Rt = cnt

#空きマスを全探索
for h in range(H):
    for w in range(W):
        if G[h][w] != -1: continue
        S = set()
        T = set()
        for p, q in D:
            u, v = h + p, w + q
            if u in range(0, H) and v in range(0, W):
                if G[u][v] != -1:
                    if UF.size(grid(u, v)) > 1:
                        S.add(UF.find(grid(u, v)))
                    else:
                        T.add(UF.find(grid(u, v)))
        #len(S)個の星座がひとつになるので cnt → cnt - len(S) + 1
        #ただし、孤立点のときは星座カウントしない
        if len(S) == len(T) == 0: continue
        if len(S):
            nxt = cnt - len(S) + 1
        if len(S) == 0 and len(T) > 0:
            nxt = cnt + 1
        if nxt < Lt: Lt = nxt
        if nxt > Rt: Rt = nxt
print(Lt, Rt)
0