Submission #1059659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059659		Gromp15	Fountain Parks (IOI21_parks)	C++17	5 / 100	274 ms	41300 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;
	vector<int> a(n-1), b(n-1), c(n-1), d(n-1);
	dsu D(n);
	int now = 0;
	vector<ar<int, 3>> ord(n);
	for (int i = 0; i < n; i++) ord[i] = {x[i], y[i], i};
	sort(all(ord));
	set<ar<int, 2>> used;
	for (int i = 0; i < n; i++) {
		int r = i;
		while (r+1 < n && ord[r+1][0] == ord[r][0] && ord[r+1][1] == ord[r][1] + 2) r++;
		for (int j = i; j < r; j++) {
			assert(D.merge(ord[j][2], ord[j+1][2]));
			a[now] = ord[j][2], b[now] = ord[j+1][2];
			if ((j - i) % 2 == 0) {
				c[now] = ord[j][0] - 1, d[now] = ord[j][1] + 1;
			}
			else {
				c[now] = ord[j][0] + 1, d[now] = ord[j][1] + 1;
			}
			//cout << "M " << ord[j][0] << " " << ord[j][1] << " " << ord[j+1][0] << " " << ord[j+1][1] << '\n';
			used.insert({c[now], d[now]});
			now++;
		}
		i = r;
	}
	for (auto [x, y, i] : ord) {
		if (idx.count({x + 2, y})) {
			int pos = idx[{x+2, y}];
			if (D.get(pos) == D.get(i)) continue;
			D.merge(pos, i);
			for (int v : {-1, 1}) if (!used.count({x + 1, y + v})) {
				a[now] = i, b[now] = pos;
				c[now] = x + 1, d[now] = y + v;
				used.insert({x + 1, y + v});
				now++;
				break;
			}
		}
	}
	/*
	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, 2>>> q;
	for (auto [x, y] : adj) q.insert({y, x});
	set<ar<int, 2>> used;
	while (q.size()) {
		auto [val, p] = *q.begin();
		q.erase(q.begin());
		if (val != adj[p]) {
			if (adj[p]) {
				q.insert({adj[p], p});
				continue;
			}
		}
		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};
		bool F = 0;
		for (int tp = 0; tp <= 4; tp++) {
			for (auto& seg : {seg2, seg3, seg4, seg5}) if (mp.count(seg) && mp[seg] == tp) {
				int i1 = idx[{seg[0], seg[1]}], i2 = idx[{seg[2], seg[3]}];
				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};
				}
				for (auto p : {pt, pt2}) adj[p]--;
				if (!F && D.get(i1) != D.get(i2)) {
					F = 1;
					D.merge(i1, i2);
					a[now] = i1, b[now] = i2;
					c[now] = p[0], d[now] = p[1];
					now++;
				}
			}
		}
		if (F) for (auto& seg : {seg2, seg3, seg4, seg5}) if (mp.count(seg)) mp[seg]--;
	}
	*/
	if (D.size[D.get(0)] != n) return 0;
	build(a, b, c, d);
	return 1;
}

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