結果
問題 | No.2696 Sign Creation |
ユーザー |
![]() |
提出日時 | 2024-03-22 22:13:32 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,091 bytes |
コンパイル時間 | 5,065 ms |
コンパイル使用メモリ | 273,000 KB |
実行使用メモリ | 10,368 KB |
最終ジャッジ日時 | 2024-12-20 11:58:53 |
合計ジャッジ時間 | 7,345 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 WA * 1 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;#define rep(i, n) for(int i=0;i<(n);++i)#define rep1(i, n) for(int i=1;i<=(n);i++)#define ll long longusing mint = modint998244353;using P = pair<ll,ll>;using lb = long double;using T = tuple<ll, ll, ll>;#ifdef LOCAL# include <debug_print.hpp># define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)#else# define dbg(...) (static_cast<void>(0))#endifint main(){int h, w, n, d;cin >> h >> w >> n >> d;vector<int> x(n), y(n);rep(i,n) cin >> x[i] >> y[i];rep(i,n) {--x[i];--y[i];}vector<vector<int>> b(h, vector<int>(w));dsu uf(h*w);rep(i,n)b[x[i]][y[i]]=1;rep(i,h)rep(j,w){if(b[i][j]) {for(int dx=-5;dx<=5;dx++)for(int dy=-5;dy<=5;dy++){if(abs(dx)+abs(dy)>d) continue;if(i+dx<0 || i+dx>=h || j+dy<0 || j+dy>=w) continue;if(b[i+dx][j+dy]) uf.merge(i*w+j, (i+dx)*w+(j+dy));}}}auto vs = uf.groups();int now = 0;for(auto v : vs) {if(v.size()>=2) now++;}int m = 1e9;int M = 0;dbg(now);rep(i,h)rep(j,w) {set<int> st;if(!b[i][j]){int c = 0;for(int dx=-5;dx<=5;dx++)for(int dy=-5;dy<=5;dy++){if(abs(dx)+abs(dy)>d) continue;if(i+dx<0 || i+dx>=h || j+dy<0 || j+dy>=w) continue;if(b[i+dx][j+dy]) {if(uf.size((i+dx)*w+j+dy)==1){c=1;}else{st.insert(uf.leader((i+dx)*w+j+dy));}}}dbg(st);if(st.size()==0) {m = min(m, now+c);M = max(M, now+c);continue;}m = min(m, (now)-(int)st.size()+1+c);M = max(M, now-(int)st.size()+1+c);}}cout << m << " " << M << endl;return 0;}