Submission #1303469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303469		jinhan814	개구리 (KOI13_frog)	C++20	2 / 19	258 ms	14528 KiB

frog

#include <bits/stdc++.h>
using namespace std;

auto sol = [](int n, int m, int k, auto v) {
	vector adj(n, vector(0, 0));
	for (int iter = 0; iter < 8; iter++) {
		vector c(0, 0);
		for (int i = 0; i < n; i++) {
			c.push_back(v[i][0]);
			c.push_back(v[i][0] + m);
		}
		sort(c.begin(), c.end());
		c.erase(unique(c.begin(), c.end()), c.end());
		vector in(c.size(), vector(0, 0));
		vector out(c.size(), vector(0, 0));
		vector buc(c.size(), vector(0, 0));
		for (int i = 0; i < n; i++) {
			int p1 = lower_bound(c.begin(), c.end(), v[i][0]) - c.begin();
			int p2 = lower_bound(c.begin(), c.end(), v[i][0] + m) - c.begin();
			in[p1].push_back(i);
			out[p2].push_back(i);
			buc[p1].push_back(i);
		}
		set s{ pair(0, 0) }; s.clear();
		for (int x = 0; x < c.size(); x++) {
			for (int i : in[x]) {
				s.insert(pair(v[i][1] + m, i));
			}
			for (int i : buc[x]) {
				if (s.begin()->first >= v[i][1]) continue;
				auto it = prev(s.lower_bound(pair(v[i][1], -1)));
				if (it->first < v[i][1] - k) continue;
				int j = it->second;
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
			for (int i : out[x]) {
				s.erase(pair(v[i][1] + m, i));
			}
		}
		for (int i = 0; i < n; i++) {
			swap(v[i][0], v[i][1]);
			v[i][1] = -v[i][1] - m;
			if (iter % 4 == 3) v[i][0] = -v[i][0] - m;
		}
	}
	vector c(n, 0);
	auto rec = [&](const auto& self, int cur) -> void {
		c[cur] = 1;
		for (int nxt : adj[cur]) {
			if (c[nxt]) continue;
			self(self, nxt);
		}
	};
	rec(rec, 0);
	int ret = 0;
	for (int i = 0; i < n; i++) {
		if (c[i] == 0) continue;
		ret = max(ret, v[i][0] + v[i][1] + 2 * m);
	}
	return ret;
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m; cin >> n >> m;
	vector v(n, array{ 0, 0 });
	for (int i = 0; i < n; i++) cin >> v[i][0] >> v[i][1];
	int k; cin >> k;
	cout << sol(n, m, k, v) << '\n';
}

• Subtask 1: 0 / 1
• Subtask 2: 2 / 2
• Subtask 3: 0 / 3
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5