Submission #773970

#	Time	Username	Problem	Language	Result	Execution time	Memory
773970		SanguineChameleon	Fountain Parks (IOI21_parks)	C++17	100 / 100	899 ms	64588 KiB

parks

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

const int maxn = 2e5 + 20;
vector<int> adj[maxn];
bool flag[maxn];
map<pair<int, int>, int> evens;

int get(int x, int y) {
	auto it = evens.find(make_pair(x, y));
	if (it == evens.end()) {
		return -1;
	}
	else {
		return it->second;
	}
}

void dfs(int u) {
	flag[u] = true;
	for (auto v: adj[u]) {
		if (!flag[v]) {
			dfs(v);
		}
	}
}

int construct_roads(vector<int> x, vector<int> y) {
	int n = x.size();
	for (int i = 0; i < n; i++) {
		evens[make_pair(x[i], y[i])] = i;
	}
	vector<pair<int, int>> roads;
	set<pair<int, int>> odds;
	for (int u = 0; u < n; u++) {
		int v = get(x[u] + 2, y[u]);
		if (v != -1) {
			odds.emplace(x[u] + 1, y[u] - 1);
			odds.emplace(x[u] + 1, y[u] + 1);
			roads.emplace_back(u, v);
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		v = get(x[u], y[u] + 2);
		if (v != -1) {
			odds.emplace(x[u] - 1, y[u] + 1);
			odds.emplace(x[u] + 1, y[u] + 1);
			roads.emplace_back(u, v);
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
	}
	dfs(0);
	for (int i = 0; i < n; i++) {
		if (!flag[i]) {
			return 0;
		}
	}
	vector<int> _u, _v, _a, _b;
	for (auto p: odds) {
		int a = p.first;
		int b = p.second;
		int u = -1;
		int v = -1;
		if ((a + b) & 2) {
			u = get(a - 1, b - 1);
			v = get(a + 1, b - 1);
			if (u != -1 && v != -1) {
				_u.push_back(u);
				_v.push_back(v);
				_a.push_back(a);
				_b.push_back(b);
			}
			else {
				u = get(a - 1, b + 1);
				v = get(a + 1, b + 1);
				if (u != -1 && v != -1) {
					_u.push_back(u);
					_v.push_back(v);
					_a.push_back(a);
					_b.push_back(b);
				}
			}
		}
		else {
			u = get(a - 1, b - 1);
			v = get(a - 1, b + 1);
			if (u != -1 && v != -1) {
				_u.push_back(u);
				_v.push_back(v);
				_a.push_back(a);
				_b.push_back(b);
			}
			else {
				u = get(a + 1, b - 1);
				v = get(a + 1, b + 1);
				if (u != -1 && v != -1) {
					_u.push_back(u);
					_v.push_back(v);
					_a.push_back(a);
					_b.push_back(b);
				}
			}
		}
	}
	build(_u, _v, _a, _b);
	return 1;
}

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