結果

問題 No.2696 Sign Creation
ユーザー navel_tosnavel_tos
提出日時 2024-03-22 22:02:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 694 ms / 2,500 ms
コード長 3,513 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 252,840 KB
最終ジャッジ日時 2024-03-27 17:58:02
合計ジャッジ時間 8,509 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
61,828 KB
testcase_01 AC 49 ms
61,832 KB
testcase_02 AC 39 ms
53,460 KB
testcase_03 AC 46 ms
61,832 KB
testcase_04 AC 41 ms
55,608 KB
testcase_05 AC 47 ms
61,916 KB
testcase_06 AC 40 ms
53,460 KB
testcase_07 AC 42 ms
53,456 KB
testcase_08 AC 126 ms
78,756 KB
testcase_09 AC 66 ms
68,304 KB
testcase_10 AC 136 ms
77,696 KB
testcase_11 AC 74 ms
72,500 KB
testcase_12 AC 75 ms
72,500 KB
testcase_13 AC 611 ms
104,180 KB
testcase_14 AC 336 ms
87,508 KB
testcase_15 AC 316 ms
88,184 KB
testcase_16 AC 536 ms
108,700 KB
testcase_17 AC 147 ms
78,768 KB
testcase_18 AC 212 ms
79,960 KB
testcase_19 AC 324 ms
83,788 KB
testcase_20 AC 85 ms
73,904 KB
testcase_21 AC 305 ms
90,804 KB
testcase_22 AC 250 ms
79,780 KB
testcase_23 AC 305 ms
85,352 KB
testcase_24 AC 309 ms
85,584 KB
testcase_25 AC 420 ms
84,316 KB
testcase_26 AC 195 ms
79,480 KB
testcase_27 AC 224 ms
79,780 KB
testcase_28 AC 228 ms
80,144 KB
testcase_29 AC 172 ms
78,956 KB
testcase_30 AC 182 ms
78,956 KB
testcase_31 AC 694 ms
252,840 KB
testcase_32 AC 46 ms
61,840 KB
testcase_33 AC 59 ms
66,160 KB
testcase_34 AC 51 ms
61,820 KB
testcase_35 AC 38 ms
53,460 KB
testcase_36 AC 38 ms
53,460 KB
testcase_37 AC 39 ms
53,460 KB
testcase_38 AC 40 ms
53,460 KB
testcase_39 AC 40 ms
53,460 KB
testcase_40 AC 40 ms
53,460 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