結果
問題 | No.2696 Sign Creation |
ユーザー |
![]() |
提出日時 | 2024-03-22 21:46:26 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 90 ms / 2,500 ms |
コード長 | 1,358 bytes |
コンパイル時間 | 4,759 ms |
コンパイル使用メモリ | 269,376 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-20 11:56:29 |
合計ジャッジ時間 | 6,664 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint998244353;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 1000000000000000001int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);int H,W,N,D;cin>>H>>W>>N>>D;vector p(H,vector<int>(W,-1));rep(i,N){int a,b;cin>>a>>b;a--,b--;p[a][b] = i;}dsu d(N);rep(i,H){rep(j,W){if(p[i][j]==-1)continue;for(int dx=-5;dx<=5;dx++){for(int dy=-5;dy<=5;dy++){if(abs(dx)+abs(dy)>D)continue;int x = i+dx,y = j+dy;if(x<0||x>=H||y<0||y>=W)continue;if(p[x][y]!=-1)d.merge(p[i][j],p[x][y]);}}}}int cur = 0;rep(i,N){if(d.leader(i)==i && d.size(i)>=2)cur++;}int m = Inf32,M = -Inf32;rep(i,H){rep(j,W){if(p[i][j]!=-1)continue;set<int> cnt;for(int dx=-5;dx<=5;dx++){for(int dy=-5;dy<=5;dy++){if(abs(dx)+abs(dy)>D)continue;int x = i+dx,y = j+dy;if(x<0||x>=H||y<0||y>=W)continue;if(p[x][y]!=-1)cnt.insert(d.leader(p[x][y]));//d.merge(p[i][j],p[x][y]);}}int x = cur;if(cnt.size()!=0){x ++;for(auto aa:cnt){if(d.size(aa)!=1)x--;}}m = min(m,x);M = max(M,x);}}cout<<m<<' '<<M<<endl;return 0;}