結果
問題 | No.2696 Sign Creation |
ユーザー |
|
提出日時 | 2024-03-22 22:39:09 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 111 ms / 2,500 ms |
コード長 | 4,250 bytes |
コンパイル時間 | 3,569 ms |
コンパイル使用メモリ | 258,180 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-20 12:11:56 |
合計ジャッジ時間 | 5,480 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
// #pragma GCC optimize("O3,unroll-loops")#include <bits/stdc++.h>// #include <x86intrin.h>using namespace std;#if __cplusplus >= 202002Lusing namespace numbers;#endifstruct disjoint_set_rollback{int n, _classes;vector<int> p;vector<pair<int, int>> recover;disjoint_set_rollback(int n): n(n), _classes(n), p(n, -1){ assert(n >= 0); }// O(1)int classes() const{return _classes;}// O(log(n))int root(int u){return p[u] < 0 ? u : root(p[u]);}// O(log(n))bool share(int a, int b){return root(a) == root(b);}// O(log(n))int size(int u){return -p[root(u)];}// O(log(n))bool merge(int u, int v){u = root(u), v = root(v);if(u == v) return false;-- _classes;if(p[u] > p[v]) swap(u, v);recover.emplace_back(v, p[v]);p[u] += p[v], p[v] = u;return true;}// O(log(n))bool merge(int u, int v, auto act){u = root(u), v = root(v);if(u == v) return false;-- _classes;bool swapped = false;if(p[u] > p[v]) swap(u, v), swapped = true;act(u, v, swapped);recover.emplace_back(v, p[v]);p[u] += p[v], p[v] = u;return true;}// Log the current state into recovervoid refresh(int signal){recover.push_back({-1, signal});}// O(1)int state(){return (int)recover.size();}// O(size(recover) - s)void reverse_to(int s){assert(s <= (int)recover.size());while((int)recover.size() > s){++ _classes;auto [u, su] = recover.back();recover.pop_back();p[p[u]] -= su, p[u] = su;}}// O(size(recover) - s)// act(-1, signal): refresh() was called with signal// act(u, v): u has been split from the child vvoid reverse_to(int s, auto act){while((int)recover.size() > s){auto [u, su] = recover.back();recover.pop_back();if(!~u) act(u, su);else{++ _classes;int pu = p[u];p[p[u]] -= su, p[u] = su;act(pu, u);}}}void clear(){_classes = n;fill(p.begin(), p.end(), -1);recover.clear();}vector<vector<int>> group_up(){vector<vector<int>> g(n);for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());return g;}friend ostream &operator<<(ostream &out, disjoint_set_rollback dsu){auto gs = dsu.group_up();out << "{";if(!gs.empty()) for(auto i = 0; i < (int)gs.size(); ++ i){out << "{";for(auto j = 0; j < (int)gs[i].size(); ++ j){out << gs[i][j];if(j + 1 < (int)gs[i].size()) out << ", ";}out << "}";if(i + 1 < (int)gs.size()) out << ", ";}return out << "}";}};int main(){cin.tie(0)->sync_with_stdio(0);cin.exceptions(ios::badbit | ios::failbit);int nr, nc, n, d;cin >> nr >> nc >> n >> d;vector<vector<int>> id(nr, vector<int>(nc, -1));for(auto i = 0; i < n; ++ i){int x, y;cin >> x >> y, -- x, -- y;id[x][y] = i;}disjoint_set_rollback dsu(nr * nc);auto index = [&](int x, int y)->int{return nc * x + y;};for(auto x = 0; x < nr; ++ x){for(auto y = 0; y < nc; ++ y){if(!~id[x][y]){continue;}for(auto nx = max(0, x - d); nx < min(x + d + 1, nr); ++ nx){for(auto ny = max(0, y - d); ny < min(y + d + 1, nc); ++ ny){if(~id[nx][ny] && abs(x - nx) + abs(y - ny) <= d){dsu.merge(index(x, y), index(nx, ny));}}}}}int iso = 0;for(auto x = 0; x < nr; ++ x){for(auto y = 0; y < nc; ++ y){if(~id[x][y] && dsu.size(index(x, y)) == 1){++ iso;}}}int resmin = numeric_limits<int>::max(), resmax = numeric_limits<int>::min();for(auto x = 0; x < nr; ++ x){for(auto y = 0; y < nc; ++ y){if(~id[x][y]){continue;}int state = dsu.state(), ciso = iso + 1;for(auto nx = max(0, x - d); nx < min(nr, x + d + 1); ++ nx){for(auto ny = max(0, y - d); ny < min(nc, y + d + 1); ++ ny){if(~id[nx][ny] && abs(x - nx) + abs(y - ny) <= d){dsu.merge(index(x, y), index(nx, ny), [&](int u, int v, bool){ciso -= (dsu.size(u) == 1) + (dsu.size(v) == 1);});}}}int cur = dsu.classes() - (nr * nc - (n + 1)) - ciso;resmin = min(resmin, cur);resmax = max(resmax, cur);dsu.reverse_to(state);}}cout << resmin << " " << resmax << "\n";return 0;}/**/