結果
問題 | No.2696 Sign Creation |
ユーザー |
![]() |
提出日時 | 2024-03-23 20:41:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 818 ms / 2,500 ms |
コード長 | 1,594 bytes |
コンパイル時間 | 248 ms |
コンパイル使用メモリ | 82,248 KB |
実行使用メモリ | 90,448 KB |
最終ジャッジ日時 | 2024-12-20 12:49:10 |
合計ジャッジ時間 | 9,521 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
def root(x):if P[x] < 0: return xP[x] = root(P[x]) # 経路圧縮return P[x]def unite(x,y):x = root(x)y = root(y)if x == y: returnif x > y: x,y = y,xP[x] += P[y]P[y] = xdef same(x,y):return root(x) == root(y)def size(x):x = root(x)return -P[x]H, W, N, D = map(int, input().split())XY = [list(map(int,input().split())) for _ in range(N)]P = [-1] * NM = [[-1] * (W+1) for _ in range(H+1)]for i,(x,y) in enumerate(XY):M[x][y] = idef search(x, y):ret = set()for i in range(-D, D+1):if 0 < x + i <= H:xi = x + ifor j in range(-D + abs(i), D - abs(i) + 1):if 0 < y + j <= W:yj = y+jif M[xi][yj] > -1:ret.add(M[xi][yj])return retfor i,(x,y) in enumerate(XY):for j in search(x,y):unite(i,j)Q = set()for i in range(N):if size(i) >= 2:Q.add(root(i))gcount = len(Q)ansmax = 0ansmin = gcountfor i in range(1,H+1):for j in range(1,W+1):if M[i][j] > -1:continuetmp = search(i,j)Q1 = set()Q2 = set()for k in tmp:if size(k) > 1:Q2.add(root(k))else:Q1.add(k)if Q2:tmp2 = gcount - len(Q2) + 1ansmax = max(ansmax, tmp2)ansmin = min(ansmin, tmp2)elif Q1:tmp2 = gcount + 1ansmax = max(ansmax,tmp2)ansmin = min(ansmin,tmp2)print(ansmin,ansmax)