結果
問題 | No.2696 Sign Creation |
ユーザー |
👑 ![]() |
提出日時 | 2024-03-22 22:59:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,500 ms |
コード長 | 3,802 bytes |
コンパイル時間 | 1,627 ms |
コンパイル使用メモリ | 117,108 KB |
最終ジャッジ日時 | 2025-02-20 12:23:21 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include <iostream> #include <string> #include <vector> #include <algorithm> #include <utility> #include <queue> #include <array> #include <cmath> #include <atcoder/modint> using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(i64 i=0; i<(i64)(n); i++) #define repr(i,n) for(i64 i=(i64)(n)-1; i>=0; i--) const i64 INF = 1001001001001001001; const char* yn(bool x){ return x ? "Yes" : "No"; } template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; } template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; } template<typename A> using nega_queue = std::priority_queue<A,std::vector<A>,std::greater<A>>; using Modint = atcoder::static_modint<998244353>; //#include "nachia/vec.hpp" #include <atcoder/dsu> using namespace std; void testcase(){ i64 H, W, N; cin >> H >> W >> N; i64 D; cin >> D; vector<pair<i64,i64>> P(N); for(auto& [x,y] : P){ cin >> x >> y; x--; y--; } sort(P.begin(), P.end()); auto dist = [&](i64 a, i64 b) -> i64 { return abs(P[a].first - P[b].first) + abs(P[a].second - P[b].second); }; vector<i64> iso(N); atcoder::dsu dsu(N); vector<vector<int>> star(H, vector<int>(W, -1)); rep(i,N) star[P[i].first][P[i].second] = i; rep(x,H) rep(y,W) if(star[x][y] >= 0) for(int dx=-D; dx<=D; dx++){ int d = D - abs(dx); for(int dy=-d; dy<=d; dy++) if(0 <= x+dx && x+dx < H && 0 <= y+dy && y+dy < W){ if(star[x+dx][y+dy] >= 0){ dsu.merge(star[x][y], star[x+dx][y+dy]); } } } rep(i,N) iso[i] = (dsu.size(i) == 1 ? 1 : 0); vector<int> C(N, -1); int ci = -1; int maxmerge = 0; int minmerge = 1001001001; rep(x,H) rep(y,W) if(star[x][y] == -1){ int count = 0; ci++; for(int dx=-D; dx<=D; dx++){ int d = D - abs(dx); for(int dy=-d; dy<=d; dy++) if(0 <= x+dx && x+dx < H && 0 <= y+dy && y+dy < W){ if(star[x+dx][y+dy] >= 0 && !iso[star[x+dx][y+dy]]){ int constellation = dsu.leader(star[x+dx][y+dy]); if(C[constellation] != ci){ C[constellation] = ci; count++; } } } } chmax(maxmerge, count); chmin(minmerge, count); } i64 a = 0; rep(i,N) if(dsu.leader(i) == i && dsu.size(i) != 1) a++; i64 lb = a - max(1, maxmerge) + 1, ub = a - max(1, minmerge) + 1; //cout << "a = " << a << endl; //cout << "maxmerge = " << maxmerge << endl; //cout << "minmerge = " << minmerge << endl; int up_ub = 0; vector<vector<int>> sp(H, vector<int>(W, -1)); rep(i,N) if(!iso[i]) sp[P[i].first][P[i].second] = D; rep(y,H) rep(x,W-1) chmax(sp[y][x+1], sp[y][x] - 1); rep(y,H) repr(x,W-1) chmax(sp[y][x], sp[y][x+1] - 1); rep(y,H-1) rep(x,W) chmax(sp[y+1][x], sp[y][x] - 1); repr(y,H-1) rep(x,W) chmax(sp[y][x], sp[y+1][x] - 1); vector<vector<int>> spiso(H, vector<int>(W, -1)); rep(i,N) if(iso[i]) spiso[P[i].first][P[i].second] = D; rep(y,H) rep(x,W-1) chmax(spiso[y][x+1], spiso[y][x] - 1); rep(y,H) repr(x,W-1) chmax(spiso[y][x], spiso[y][x+1] - 1); rep(y,H-1) rep(x,W) chmax(spiso[y+1][x], spiso[y][x] - 1); repr(y,H-1) rep(x,W) chmax(spiso[y][x], spiso[y+1][x] - 1); rep(y,H) rep(x,W) if(spiso[y][x] >= 0 && spiso[y][x] != D && sp[y][x] < 0) up_ub++; //cout << "up_ub = " << up_ub << endl; if(up_ub){ ub = a + 1; if(up_ub + N == H*W) lb = ub; } cout << lb << " " << ub << "\n"; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); #ifdef NACHIA int T; cin >> T; for(int t=0; t<T; T!=++t?(cout<<'\n'),0:0) #endif testcase(); return 0; }