Submission #773466

#	Time	Username	Problem	Language	Result	Execution time	Memory
773466		SanguineChameleon	Fountain Parks (IOI21_parks)	C++17	45 / 100	925 ms	104600 KiB

parks

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

const int maxn = 2e5 + 20;
vector<int> adj[maxn * 3];
bool flag[maxn * 3];
map<pair<int, int>, int> even_id;
map<pair<int, int>, int> odd_id;
vector<pair<int, int>> odds;
vector<pair<int, int>> roads;
int node_cnt;
int road_cnt;
vector<int> path;

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

int get_odd_id(int x, int y) {
	auto it = odd_id.find(make_pair(x, y));
	if (it != odd_id.end()) {
		return it->second;
	}
	else {
		odds.emplace_back(x, y);
		return odd_id[make_pair(x, y)] = node_cnt++;
	}
}

void add_edge(int u, int v) {
	adj[u].push_back(v);
	adj[v].push_back(u);
}

void dfs(int u) {
	flag[u] = true;
	path.push_back(u);
	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++) {
		even_id[make_pair(x[i], y[i])] = i;
	}
	for (int u = 0; u < n; u++) {
		int v = get_even_id(x[u] + 2, y[u]);
		if (v != -1) {
			roads.emplace_back(u, v);
			add_edge(u, v);
		}
		v = get_even_id(x[u], y[u] + 2);
		if (v != -1) {
			roads.emplace_back(u, v);
			add_edge(u, v);
		}
	}
	dfs(0);
	for (int i = 0; i < n; i++) {
		if (!flag[i]) {
			return 0;
		}
	}
	for (int i = 0; i < n; i++) {
		adj[i].clear();
	}
	road_cnt = roads.size();
	node_cnt = road_cnt;
	for (int i = 0; i < road_cnt; i++) {
		int u = roads[i].first;
		int v = roads[i].second;
		if (y[u] == y[v]) {
			add_edge(i, get_odd_id(x[u] + 1, y[u] - 1));
			add_edge(i, get_odd_id(x[u] + 1, y[u] + 1));
		}
		else {
			add_edge(i, get_odd_id(x[u] - 1, y[u] + 1));
			add_edge(i, get_odd_id(x[u] + 1, y[u] + 1));
		}
	}
	vector<int> u, v, a, b;
	for (int i = 0; i < node_cnt; i++) {
		flag[i] = false;
	}
	for (int iter = 0; iter < 2; iter++) {
		for (int i = road_cnt; i < node_cnt; i++) {
			if (!flag[i] && (iter == 1 || (int)adj[i].size() == 1)) {
				path.clear();
				dfs(i);
				for (int j = 0; j + 1 < (int)path.size(); j += 2) {
					u.push_back(roads[path[j + 1]].first);
					v.push_back(roads[path[j + 1]].second);
					a.push_back(odds[path[j] - road_cnt].first);
					b.push_back(odds[path[j] - road_cnt].second);
				}
			}
		}
	}
	build(u, v, a, b);
	return 1;
}

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