結果
問題 | No.2696 Sign Creation |
ユーザー | Aeren |
提出日時 | 2024-03-22 22:39:09 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 109 ms / 2,500 ms |
コード長 | 4,250 bytes |
コンパイル時間 | 3,493 ms |
コンパイル使用メモリ | 258,416 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-05-17 18:14:55 |
合計ジャッジ時間 | 5,066 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,948 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 3 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 4 ms
6,944 KB |
testcase_11 | AC | 3 ms
6,940 KB |
testcase_12 | AC | 3 ms
6,940 KB |
testcase_13 | AC | 109 ms
6,940 KB |
testcase_14 | AC | 35 ms
6,940 KB |
testcase_15 | AC | 31 ms
6,944 KB |
testcase_16 | AC | 97 ms
6,944 KB |
testcase_17 | AC | 22 ms
6,940 KB |
testcase_18 | AC | 16 ms
6,944 KB |
testcase_19 | AC | 42 ms
6,940 KB |
testcase_20 | AC | 4 ms
6,944 KB |
testcase_21 | AC | 20 ms
6,940 KB |
testcase_22 | AC | 29 ms
6,944 KB |
testcase_23 | AC | 31 ms
6,940 KB |
testcase_24 | AC | 31 ms
6,944 KB |
testcase_25 | AC | 52 ms
6,940 KB |
testcase_26 | AC | 23 ms
6,944 KB |
testcase_27 | AC | 26 ms
6,940 KB |
testcase_28 | AC | 19 ms
6,944 KB |
testcase_29 | AC | 24 ms
6,944 KB |
testcase_30 | AC | 23 ms
6,940 KB |
testcase_31 | AC | 70 ms
6,944 KB |
testcase_32 | AC | 2 ms
6,940 KB |
testcase_33 | AC | 3 ms
6,940 KB |
testcase_34 | AC | 2 ms
6,944 KB |
testcase_35 | AC | 2 ms
6,940 KB |
testcase_36 | AC | 2 ms
6,944 KB |
testcase_37 | AC | 2 ms
6,944 KB |
testcase_38 | AC | 2 ms
6,940 KB |
testcase_39 | AC | 2 ms
6,944 KB |
testcase_40 | AC | 2 ms
6,940 KB |
ソースコード
// #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> // #include <x86intrin.h> using namespace std; #if __cplusplus >= 202002L using namespace numbers; #endif struct 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 recover void 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 v void 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; } /* */