結果
問題 | No.2696 Sign Creation |
ユーザー |
![]() |
提出日時 | 2024-03-22 22:32:53 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,377 bytes |
コンパイル時間 | 2,816 ms |
コンパイル使用メモリ | 216,684 KB |
実行使用メモリ | 7,808 KB |
最終ジャッジ日時 | 2024-12-20 12:10:15 |
合計ジャッジ時間 | 4,961 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 WA * 1 |
ソースコード
#include <bits/stdc++.h>#define int llusing namespace std;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define rng(i,c,n) for(int i=c;i<n;i++)#define fi first#define se second#define pb push_back#define all(a) a.begin(), a.end()#define sz(a) ((int) a.size())#define vec(...) vector<__VA_ARGS__>#define _4ab8goq ios::sync_with_stdio(0),cin.tie(0);typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pii;void print(){cout<<'\n';}template<class h,class...t>void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}struct dsu{int _n;vi si,par,leb;dsu(int n=0){init(n);}void init(int n=0){_n=n;par=vi(_n,0);si=vi(_n,0);leb=vi(_n,-1);rep(i,n){si[i]=1;par[i]=i;}}int parent(int u){return par[u]=(par[u]==u?u:parent(par[u]));}bool same(int u,int v){return parent(u)==parent(v);}void merge(int u,int v){u=parent(u),v=parent(v);if(!same(u,v)){if(si[u]<si[v]) swap(u,v);leb[u]=max(leb[u],leb[v]);_n-=1;si[u]+=si[v];par[v]=u;}}int size(int v=-1){return v==-1?_n:si[parent(v)];}};void slv(){int h,w,n,d;cin>>h>>w>>n>>d;vec(pii) a(n);rep(i,n){cin>>a[i].fi>>a[i].se;}rep(i,n){a[i].fi-=1,a[i].se-=1;}vi qs(h*w,-1);rep(i,n){qs[a[i].fi*w+a[i].se]=i;}auto ok=[&](int i,int j){return min(i,j)>=0 and i<h and j<w;};dsu uf(n);rep(i,n){auto [x,y]=a[i];rng(di,-d,d+1){rng(dj,-d,d+1){if(abs(di)+abs(dj)>d) continue;int nx=x+di,ny=y+dj;if(ok(nx,ny) and qs[nx*w+ny]!=-1){uf.merge(i,qs[nx*w+ny]);}}}}int cnt=0;rep(i,n){if(uf.parent(i)==i){if(uf.size(i)>1){cnt+=1;}}}int mi=1e9,ma=0;rep(i,h){rep(j,w){int x=i,y=j;vi evs;rng(di,-d,d+1){rng(dj,-d,d+1){if(abs(di)+abs(dj)>d) continue;int nx=x+di,ny=y+dj;if(ok(nx,ny) and qs[nx*w+ny]!=-1){// st.insert(uf.parent(mp[nx*w+ny]));evs.pb(uf.parent(qs[nx*w+ny]));}}}sort(all(evs));evs.erase(unique(all(evs)),evs.end());int now=cnt,e=0;for(auto v:evs){if(uf.size(v)>1){e+=1;}}// if(i==3 and j==2) print(sz(st),e);if(!e){now+=(sz(evs)>0);}else{now-=(e-1);}mi=min(mi,now);ma=max(ma,now);}}cout<<mi<<" "<<ma<<"\n";}signed main(){_4ab8goq;slv();}