結果
問題 | No.2696 Sign Creation |
ユーザー |
![]() |
提出日時 | 2024-03-22 22:13:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,091 bytes |
コンパイル時間 | 4,749 ms |
コンパイル使用メモリ | 260,088 KB |
最終ジャッジ日時 | 2025-02-20 11:45:23 |
ジャッジサーバーID (参考情報) |
judge1 / 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 long using 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)) #endif int 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; }