結果

問題 No.2696 Sign Creation
ユーザー navel_tosnavel_tos
提出日時 2024-03-22 22:02:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 661 ms / 2,500 ms
コード長 3,513 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 253,224 KB
最終ジャッジ日時 2024-05-17 18:11:08
合計ジャッジ時間 8,303 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
60,828 KB
testcase_01 AC 46 ms
61,848 KB
testcase_02 AC 39 ms
53,664 KB
testcase_03 AC 47 ms
61,304 KB
testcase_04 AC 43 ms
54,364 KB
testcase_05 AC 48 ms
62,480 KB
testcase_06 AC 41 ms
54,172 KB
testcase_07 AC 40 ms
53,796 KB
testcase_08 AC 131 ms
79,280 KB
testcase_09 AC 67 ms
68,772 KB
testcase_10 AC 137 ms
78,284 KB
testcase_11 AC 74 ms
71,800 KB
testcase_12 AC 74 ms
73,252 KB
testcase_13 AC 596 ms
104,360 KB
testcase_14 AC 330 ms
87,936 KB
testcase_15 AC 311 ms
88,712 KB
testcase_16 AC 539 ms
109,116 KB
testcase_17 AC 147 ms
79,004 KB
testcase_18 AC 214 ms
80,380 KB
testcase_19 AC 317 ms
84,336 KB
testcase_20 AC 86 ms
74,704 KB
testcase_21 AC 297 ms
91,600 KB
testcase_22 AC 244 ms
80,624 KB
testcase_23 AC 296 ms
85,920 KB
testcase_24 AC 301 ms
86,124 KB
testcase_25 AC 419 ms
84,988 KB
testcase_26 AC 192 ms
80,584 KB
testcase_27 AC 220 ms
80,316 KB
testcase_28 AC 218 ms
80,560 KB
testcase_29 AC 167 ms
79,588 KB
testcase_30 AC 177 ms
79,540 KB
testcase_31 AC 661 ms
253,224 KB
testcase_32 AC 46 ms
62,448 KB
testcase_33 AC 56 ms
66,096 KB
testcase_34 AC 50 ms
62,504 KB
testcase_35 AC 39 ms
54,376 KB
testcase_36 AC 39 ms
53,916 KB
testcase_37 AC 39 ms
53,188 KB
testcase_38 AC 38 ms
53,784 KB
testcase_39 AC 40 ms
54,280 KB
testcase_40 AC 41 ms
54,684 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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