Submission #987010

#	Time	Username	Problem	Language	Result	Execution time	Memory
987010		pedroslrey	Fountain Parks (IOI21_parks)	C++17	15 / 100	366 ms	32776 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"

using namespace std;

int construct_roads(vector<int> xs, vector<int> ys) {
	int n = xs.size();

	map<pair<int, int>, int> points;
	for (int i = 0; i < n; ++i)
		points[make_pair(xs[i], ys[i])] = i;

	vector<int> rep(n); int comps = n;
	for (int i = 0; i < n; ++i)
		rep[i] = i;

	function<int (int)> find = [&rep, &find](int u) {
		if (rep[u] == u) return u;
		return rep[u] = find(rep[u]);
	};

	function<void (int, int)> une = [&rep, &comps, &find](int u, int v) {
		u = find(u); v = find(v);

		if (u == v) return;
		rep[u] = v;

		--comps;
	};

	vector<int> us, vs, as, bs;
	for (int i = 0; i < n; ++i) {
		int x = xs[i], y = ys[i];
		if (points.find(make_pair(x + 2, y)) != points.end()) {
			us.push_back(i);
			vs.push_back(points[make_pair(x + 2, y)]);
			une(us.back(), vs.back());

			as.push_back(3);
			bs.push_back(y + 1);
		}
		if (points.find(make_pair(x, y + 2)) != points.end()) {
			us.push_back(i);
			vs.push_back(points[make_pair(x, y + 2)]);
			une(us.back(), vs.back());

			if (x == 2) {
				as.push_back(1);
				bs.push_back(y + 1);
			}
			else {
				as.push_back(5);
				bs.push_back(y + 1);
			}
		}
	}

	if (comps > 1) return 0;

	build(us, vs, as, bs);

	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