結果
問題 | No.2696 Sign Creation |
ユーザー | とりゐ |
提出日時 | 2024-03-22 21:58:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,350 ms / 2,500 ms |
コード長 | 2,702 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 111,260 KB |
最終ジャッジ日時 | 2024-03-27 17:57:54 |
合計ジャッジ時間 | 8,727 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
55,608 KB |
testcase_01 | AC | 42 ms
55,608 KB |
testcase_02 | AC | 43 ms
55,608 KB |
testcase_03 | AC | 43 ms
55,608 KB |
testcase_04 | AC | 44 ms
55,608 KB |
testcase_05 | AC | 43 ms
55,608 KB |
testcase_06 | AC | 43 ms
55,608 KB |
testcase_07 | AC | 47 ms
55,608 KB |
testcase_08 | AC | 143 ms
77,072 KB |
testcase_09 | AC | 46 ms
57,680 KB |
testcase_10 | AC | 162 ms
78,320 KB |
testcase_11 | AC | 53 ms
63,788 KB |
testcase_12 | AC | 52 ms
63,788 KB |
testcase_13 | AC | 545 ms
89,792 KB |
testcase_14 | AC | 410 ms
89,164 KB |
testcase_15 | AC | 387 ms
89,212 KB |
testcase_16 | AC | 541 ms
89,328 KB |
testcase_17 | AC | 63 ms
72,468 KB |
testcase_18 | AC | 211 ms
82,448 KB |
testcase_19 | AC | 366 ms
85,472 KB |
testcase_20 | AC | 73 ms
73,216 KB |
testcase_21 | AC | 335 ms
88,032 KB |
testcase_22 | AC | 194 ms
82,272 KB |
testcase_23 | AC | 351 ms
85,728 KB |
testcase_24 | AC | 343 ms
85,856 KB |
testcase_25 | AC | 354 ms
85,216 KB |
testcase_26 | AC | 130 ms
79,924 KB |
testcase_27 | AC | 166 ms
82,912 KB |
testcase_28 | AC | 173 ms
82,784 KB |
testcase_29 | AC | 89 ms
81,016 KB |
testcase_30 | AC | 93 ms
81,040 KB |
testcase_31 | AC | 1,350 ms
111,260 KB |
testcase_32 | AC | 42 ms
55,608 KB |
testcase_33 | AC | 47 ms
61,544 KB |
testcase_34 | AC | 52 ms
64,044 KB |
testcase_35 | AC | 43 ms
55,608 KB |
testcase_36 | AC | 43 ms
55,608 KB |
testcase_37 | AC | 42 ms
55,608 KB |
testcase_38 | AC | 42 ms
55,608 KB |
testcase_39 | AC | 43 ms
55,608 KB |
testcase_40 | AC | 43 ms
55,608 KB |
ソースコード
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)