結果
問題 | No.2696 Sign Creation |
ユーザー |
![]() |
提出日時 | 2024-03-26 15:57:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 732 ms / 2,500 ms |
コード長 | 3,656 bytes |
コンパイル時間 | 674 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 90,932 KB |
最終ジャッジ日時 | 2024-12-20 12:52:09 |
合計ジャッジ時間 | 11,841 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
# D小さい、HW積小さい、Union Findでまず星をつなげて、それから空きマスからルート探索# 最小値最大値を求めるのが面倒class UnionFind():def __init__(self, n):self.n = nself.parents = [-1] * ndef find(self, x):if self.parents[x] < 0:return xelse:self.parents[x] = self.find(self.parents[x])return self.parents[x]def unite(self, x, y):x = self.find(x)y = self.find(y)if x == y:returnif self.parents[x] > self.parents[y]:x, y = y, xself.parents[x] += self.parents[y]self.parents[y] = xdef size(self, x):return -self.parents[self.find(x)]def same(self, x, y):return self.find(x) == self.find(y)def members(self, x):root = self.find(x)return [i for i in range(self.n) if self.find(i) == root]def roots(self):return [i for i, x in enumerate(self.parents) if x < 0]def group_count(self):return len(self.roots())def all_group_members(self):group_members = defaultdict(list)for member in range(self.n):group_members[self.find(member)].append(member)return group_membersdef __str__(self):return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())H, W, N, D = map(int, input().split())board = [[-1]*W for i in range(H)]XY = []for i in range(N):x, y = map(int, input().split())x -= 1y -= 1XY.append((x, y))board[x][y] = ifrom collections import defaultdictUF = UnionFind(N)for h in range(H):for w in range(W):if board[h][w]>=0:for dh in range(max(0, h-D), min(H, h+D+1)):for dw in range(max(0, w-D), min(W, w+D+1)):if (dh, dw)==(h, w):continueif board[dh][dw]>=0:if abs(h-dh)+abs(w-dw)<= D:UF.unite(board[h][w], board[dh][dw])initial_count = 0for members in UF.all_group_members().values():#print(members, len(members))if len(members)>=2:initial_count += 1#print('initial_count', initial_count)mn = initial_countmx = initial_countfor h in range(H):for w in range(W):if board[h][w]==-1:seiza = 0star = 0root_visited = set()for dh in range(max(0, h-D), min(H, h+D+1)):for dw in range(max(0, w-D), min(W, w+D+1)):if (dh, dw)==(h, w):continueif board[dh][dw]>=0:if abs(h-dh)+abs(w-dw)<= D:r = UF.find(board[dh][dw])if r not in root_visited:root_visited.add(r)if UF.size(r) == 1:star += 1elif UF.size(r) >= 2:seiza += 1#print('h', h, 'w', w, 'seiza', seiza, 'star', star)if seiza == 0:if star >= 1:mn = min(mn, initial_count+1)mx = max(mx, initial_count+1)elif seiza == 1:passelif seiza >= 2:mn = min(mn, initial_count-(seiza-1))mx = max(mx, initial_count-(seiza-1))#print('mn', mn, 'mx', mx)#print()print(mn, mx)