#964188 (C++23) No.2696 Sign Creation

提出ソース

結果

問題	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

権限があれば一括ダウンロードができます

ソースコード

raw source code

// #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;
}

/*

*/

yukicoder

結果

テストケース

ソースコード