結果
問題 | No.2696 Sign Creation |
ユーザー |
![]() |
提出日時 | 2024-03-23 10:46:07 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,044 bytes |
コンパイル時間 | 249 ms |
コンパイル使用メモリ | 82,296 KB |
実行使用メモリ | 79,820 KB |
最終ジャッジ日時 | 2024-12-20 12:44:38 |
合計ジャッジ時間 | 8,808 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 12 WA * 26 |
ソースコード
h,w,n,d=map(int,input().split()) a=[[-1]*w for i in range(h)] r=list(range(n)) v=[1]*n def union(x,y): rx=root(x) ry=root(y) if rx>ry: rx,ry=ry,rx r[ry]=rx v[rx]+=v[ry] v[ry]=0 return def root(x): p=x l=[p] while r[p]!=p: p=r[p] l.append(p) for p in l: r[p]=l[-1] return r[x] dxdy=[] for dx in range(-d,d+1): for dy in range(-d,d+1): if 1<=abs(dx)+abs(dy)<=d: dxdy+=[(dx,dy)] for i in range(n): x,y=map(int,input().split()) x-=1 y-=1 a[x][y]=i for x in range(h): for y in range(w): if a[x][y]!=-1: for dx,dy in dxdy: xx=x+dx yy=y+dy if 0<=xx<h and 0<=yy<w and a[xx][yy]!=-1: union(a[x][y],a[xx][yy]) g0=len(set([r[i] for i in range(n) if v[i]>1])) g1=g0 g2=0 f=0 for x in range(h): for y in range(w): if a[x][y]==-1: rr=set() for dx,dy in dxdy: xx=x+dx yy=y+dy if 0<=xx<h and 0<=yy<w and a[xx][yy]!=-1: ra=root(a[xx][yy]) if v[ra]>1: rr.add(ra) else: f|=1 ll=len(rr) if ll>0: g2=min(g2,-ll+1) print(g0+g2,g1+f)