結果
問題 | No.2696 Sign Creation |
ユーザー |
|
提出日時 | 2024-03-22 23:40:43 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,026 bytes |
コンパイル時間 | 412 ms |
コンパイル使用メモリ | 81,756 KB |
実行使用メモリ | 101,876 KB |
最終ジャッジ日時 | 2024-12-20 12:34:54 |
合計ジャッジ時間 | 7,637 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 WA * 1 |
ソースコード
class UnionFind:def __init__(self, n, w=None):self.par = [-1]*nself.rank = [0]*nself.siz = [1]*nself.cnt = nself.min_node = [i for i in range(n)]self.weight = w if w else [1]*ndef root(self, x):if self.par[x] == -1:return xself.par[x] = self.root(self.par[x])return self.par[x]def issame(self, x, y):return self.root(x) == self.root(y)def unite(self, x, y):px = self.root(x)py = self.root(y)if px == py:return Falseif self.rank[px] < self.rank[py]:px, py = py, pxself.par[py] = pxif self.rank[px] == self.rank[py]:self.rank[px] += 1self.siz[px] += self.siz[py]self.cnt -= 1self.min_node[px] = min(self.min_node[px], self.min_node[py])self.weight[px] += self.weight[py]return Falsedef count(self):return self.cntdef min(self, x):return self.min_node[self.root(x)]def getweight(self, x):return self.weight[self.root(x)]def size(self, x):return self.siz[self.root(x)]import sysinput = sys.stdin.readlineH, W, N, D = map(int, input().split())XY = [list(map(int, input().split())) for _ in range(N)]field = [[-1 for _ in range(W)] for _ in range(H)]for i in range(N):x, y = XY[i]x-=1y-=1field[x][y] = iXY[i] = [x, y]man = set()for i in range(D+1):for j in range(D+1):if i+j<=D:man.add((i, j))if i!=0:man.add((-i, j))if j!=0:man.add((i, -j))if i!=0 and j!=0:man.add((-i, -j))else:breakfield2 = [[0 for _ in range(W)] for _ in range(H)]UF = UnionFind(N)for i in range(N):x, y = XY[i]for dx, dy in man:nx = x+dxny = y+dyif 0<=nx<H and 0<=ny<W:field2[nx][ny] += 1if field[nx][ny]!=-1:j = field[nx][ny]UF.unite(i, j)max_cnt = 0for i in range(N):if UF.size(i)==1:x, y = XY[i]for dx, dy in man:nx = x+dxny = y+dyif 0<=nx<H and 0<=ny<W:if field2[nx][ny]==1 and field[nx][ny]==-1:max_cnt = 1breakif max_cnt==1:breakfield3 = [[0 for _ in range(W)] for _ in range(H)]S = dict()cnt = 0for i in range(N):x, y = XY[i]if UF.size(i)==1:cnt+=1continuer = UF.root(i)if r not in S:S[r] = set()for dx, dy in man:nx = x+dxny = y+dyif 0<=nx<H and 0<=ny<W and field[nx][ny]==-1:S[r].add((nx, ny))min_cnt = 0for r in S:for x, y in S[r]:field3[x][y] += 1min_cnt = max(min_cnt, field3[x][y])if min_cnt>0:min_cnt-=1print(UF.count()-cnt-min_cnt, UF.count()-cnt+max_cnt)