結果
問題 | 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 defaultdict class UnionFind(): def __init__(self,n): self.n=n self.parents=[-1]*n self.group_count=n def find(self,x): if self.parents[x]<0: return x else: 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: return if self.parents[x]>self.parents[y]: x,y=y,x self.parents[x]+=self.parents[y] self.parents[y]=x self.group_count-=1 def 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_members from collections import deque H,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]=i xy.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: continue for dx,dy in dxdy: nx,ny=x0+dx,y0+dy if 0<=nx<H and 0<=ny<W: if seen[nx][ny]!=i: seen[nx][ny]=i todo.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=0 for i in g: if len(g[i])>1: sz+=1 todo=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: continue for dx,dy in dxdy: nx,ny=x0+dx,y0+dy if 0<=nx<H and 0<=ny<W: if seen[nx][ny]!=i: seen[nx][ny]=i cnt[nx][ny]+=1 if len(g[i])!=1: cnt2[nx][ny]+=1 todo.append([d0+1,nx,ny]) if len(g[i])==1: mark[nx][ny]=1 mn=1<<30 mx=-1 for 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)