Submission #1059616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059616		Gromp15	Fountain Parks (IOI21_parks)	C++17	15 / 100	1393 ms	78884 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

struct dsu {
	vector<int> p, size;
	dsu(int n) : p(n), size(n, 1) {
		iota(all(p), 0);
	}
	int get(int v) {
		return v == p[v] ? v : p[v] = get(p[v]);
	}
	bool merge(int a, int b) {
		a = get(a), b = get(b);
		if (a == b) return 0;
		if (size[a] < size[b]) swap(a, b);
		size[a] += size[b], p[b] = a;
		return 1;
	}
};

int construct_roads(std::vector<int> x, std::vector<int> y) {
	int n = sz(x);
	map<ar<int, 4>, int> mp;
	map<ar<int, 2>, int> idx;
	for (int i = 0; i < n; i++) idx[{x[i], y[i]}] = i;
	map<ar<int, 2>, int> adj;
	for (int i = 0; i < n; i++) {
		if (idx.count({x[i] + 2, y[i]})) {
			mp[{x[i], y[i], x[i] + 2, y[i]}] += 2;
			adj[{x[i] + 1, y[i] + 1}]++;
			adj[{x[i] + 1, y[i] - 1}]++;
		}
		if (idx.count({x[i], y[i] + 2})) {
			mp[{x[i], y[i], x[i], y[i] + 2}] += 2;
			adj[{x[i] + 1, y[i] + 1}]++;
			adj[{x[i] - 1, y[i] + 1}]++;
		}
	}
	set<pair<int, ar<int, 4>>> q;
	for (auto [x, y] : mp) q.insert({y, x});
	dsu D(n);
	vector<int> a(n-1), b(n-1), c(n-1), d(n-1);
	set<ar<int, 2>> used;
	int now = 0;
	while (q.size()) {
		auto [val, seg] = *q.begin();
		q.erase(q.begin());
		if (mp[seg] != val) {
			if (mp[seg]) {
				q.insert({mp[seg], seg});
				continue;
			}
		}
		int i1 = idx[{seg[0], seg[1]}], i2 = idx[{seg[2], seg[3]}];
		if (D.get(i1) == D.get(i2)) continue;
		if (val) {
			ar<int, 2> pt, pt2;
			if (seg[0] != seg[2]) {
				pt = {seg[0] + 1, seg[1] - 1};
				pt2 = {seg[0] + 1, seg[1] + 1};
			}
			else {
				pt = {seg[0] - 1, seg[1] + 1};
				pt2 = {seg[0] + 1, seg[1] + 1};
			}
			bool F = 0;
			for (auto p : {pt, pt2}) if (adj[p] == 1) {
				if (!used.count(p)) {
					F = 1;
					used.insert(p);
					D.merge(i1, i2);
					a[now] = i1, b[now] = i2;
					c[now] = p[0], d[now] = p[1];
					now++;
					ar<int, 4> seg2{p[0] - 1, p[1] - 1, p[0] - 1, p[1] + 1};
					ar<int, 4> seg3{p[0] + 1, p[1] - 1, p[0] + 1, p[1] + 1};
					ar<int, 4> seg4{p[0] - 1, p[1] - 1, p[0] + 1, p[1] - 1};
					ar<int, 4> seg5{p[0] - 1, p[1] + 1, p[0] + 1, p[1] + 1};
					if (mp.count(seg2)) mp[seg2]--;
					if (mp.count(seg3)) mp[seg3]--;
					if (mp.count(seg4)) mp[seg4]--;
					if (mp.count(seg5)) mp[seg5]--;
					break;
				}
			}
			if (!F) {
				for (auto p : {pt, pt2}) if (adj[p] == 2) {
					if (!used.count(p)) {
						F = 1;
						used.insert(p);
						D.merge(i1, i2);
						a[now] = i1, b[now] = i2;
						c[now] = p[0], d[now] = p[1];
						now++;
						ar<int, 4> seg2{p[0] - 1, p[1] - 1, p[0] - 1, p[1] + 1};
						ar<int, 4> seg3{p[0] + 1, p[1] - 1, p[0] + 1, p[1] + 1};
						ar<int, 4> seg4{p[0] - 1, p[1] - 1, p[0] + 1, p[1] - 1};
						ar<int, 4> seg5{p[0] - 1, p[1] + 1, p[0] + 1, p[1] + 1};
						if (mp.count(seg2)) mp[seg2]--;
						if (mp.count(seg3)) mp[seg3]--;
						if (mp.count(seg4)) mp[seg4]--;
						if (mp.count(seg5)) mp[seg5]--;
						break;
					}
				}
				assert(F);
			}
			for (auto p : {pt, pt2}) {
				adj[p]--;
			}
		}
	}
	if (D.size[D.get(0)] != n) return 0;
	build(a, b, c, d);
	return 1;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30