結果
問題 | No.2696 Sign Creation |
ユーザー |
![]() |
提出日時 | 2024-03-22 21:58:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,576 ms / 2,500 ms |
コード長 | 2,702 bytes |
コンパイル時間 | 303 ms |
コンパイル使用メモリ | 82,408 KB |
実行使用メモリ | 111,184 KB |
最終ジャッジ日時 | 2024-12-20 11:57:35 |
合計ジャッジ時間 | 10,057 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
from collections import defaultdictclass UnionFind():def __init__(self,n):self.n=nself.parents=[-1]*nself.group_count=ndef find(self,x):if self.parents[x]<0:return xelse:self.parents[x]=self.find(self.parents[x])return self.parents[x]def union(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]=xself.group_count-=1def 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 groups(self):group_members=defaultdict(list)for member in range(self.n):group_members[self.find(member)].append(member)return group_membersfrom collections import dequeH,W,N,D=map(int,input().split())mat=[[-1]*W for i in range(H)]xy=[]for i in range(N):x,y=map(lambda x:int(x)-1,input().split())mat[x][y]=ixy.append([x,y])dxdy=[(1,0),(0,1),(-1,0),(0,-1)]uf=UnionFind(N)seen=[[-1]*W for i in range(H)]for i in range(N):x,y=xy[i]todo=deque()todo.append([0,x,y])while todo:d0,x0,y0=todo.popleft()if mat[x0][y0]!=-1:uf.union(i,mat[x0][y0])if d0==D:continuefor dx,dy in dxdy:nx,ny=x0+dx,y0+dyif 0<=nx<H and 0<=ny<W:if seen[nx][ny]!=i:seen[nx][ny]=itodo.append([d0+1,nx,ny])g=uf.groups()seen=[[-1]*W for i in range(H)]cnt=[[0]*W for i in range(H)]cnt2=[[0]*W for i in range(H)]mark=[[0]*W for i in range(H)]sz=0for i in g:if len(g[i])>1:sz+=1todo=deque()for j in g[i]:x,y=xy[j]todo.append([0,x,y])while todo:d0,x0,y0=todo.popleft()if d0==D:continuefor dx,dy in dxdy:nx,ny=x0+dx,y0+dyif 0<=nx<H and 0<=ny<W:if seen[nx][ny]!=i:seen[nx][ny]=icnt[nx][ny]+=1if len(g[i])!=1:cnt2[nx][ny]+=1todo.append([d0+1,nx,ny])if len(g[i])==1:mark[nx][ny]=1mn=1<<30mx=-1for x in range(H):for y in range(W):if mat[x][y]==-1:if cnt[x][y]==0:mn=min(mn,sz)mx=max(mx,sz)else:if cnt[x][y]==1:if mark[x][y]==1:mx=max(mx,sz+1)mn=min(mn,sz+1)else:mx=max(mx,sz)mn=min(mn,sz)else:mx=max(mx,sz-cnt2[x][y]+1)mn=min(mn,sz-cnt2[x][y]+1)print(mn,mx)