結果

問題 No.2696 Sign Creation
ユーザー AerenAeren
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #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;
}
/*
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0