Submission #1069158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069158		mickey080929	Fountain Parks (IOI21_parks)	C++17	100 / 100	1278 ms	60916 KiB

parks

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

using namespace std;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);

struct DisjointSet{
	vector<int> par;
	void init(int n) {
		par.resize(n);
		iota(par.begin(), par.end(), 0);
	}
	int Find(int x) {
		if (x == par[x]) return x;
		return par[x] = Find(par[x]);
	}
	void Union(int x, int y) {
		x = Find(x);
		y = Find(y);
		par[y] = x;
	}
};

DisjointSet dsu;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int construct_roads(vector<int> x, vector<int> y) {
	int N = x.size();
	set<pair<int,int>> bench;
	map<pair<int,int>,int> num;
	for (int i=0; i<N; i++) {
		num[{x[i], y[i]}] = i;
		bench.insert({x[i]+1, y[i]+1});
		bench.insert({x[i]+1, y[i]-1});
		bench.insert({x[i]-1, y[i]+1});
		bench.insert({x[i]-1, y[i]-1});
	}
	dsu.init(N);
	set<pair<int,int>> ban;
	vector<pair<int,int>> edge;
	for (auto &[X, Y] : bench) {
		if (num.find({X+1, Y+1}) == num.end()) continue;
		if (num.find({X+1, Y-1}) == num.end()) continue;
		if (num.find({X-1, Y+1}) == num.end()) continue;
		if (num.find({X-1, Y-1}) == num.end()) continue;

		int v1 = num[{X-1, Y-1}], v2 = num[{X-1, Y+1}], v3 = num[{X+1, Y+1}], v4 = num[{X+1, Y-1}];
		if ((X + Y) % 4 == 0) {
			if (dsu.Find(v2) != dsu.Find(v3)) {
				dsu.Union(v2, v3);
				edge.emplace_back(v2, v3);
			}
			if (dsu.Find(v3) != dsu.Find(v4)) {
				dsu.Union(v3, v4);
				edge.emplace_back(v3, v4);
			}
			ban.insert({v1, v4});
			ban.insert({v4, v1});
		}
		else {
			if (dsu.Find(v1) != dsu.Find(v2)) {
				dsu.Union(v1, v2);
				edge.emplace_back(v1, v2);
			}
			if (dsu.Find(v1) != dsu.Find(v4)) {
				dsu.Union(v1, v4);
				edge.emplace_back(v1, v4);
			}
			ban.insert({v3, v4});
			ban.insert({v4, v3});
		}
	}
	for (int i=0; i<N; i++) {
		for (int k=0; k<4; k++) {
			int nx = x[i] + dx[k] * 2;
			int ny = y[i] + dy[k] * 2;
			if (num.find({nx, ny}) == num.end()) continue;
			if (dsu.Find(num[{nx, ny}]) != dsu.Find(i)) {
				if (ban.find({num[{nx, ny}], i}) == ban.end()) {
					dsu.Union(num[{nx, ny}], i);
					edge.emplace_back(num[{nx, ny}], i);
				}
			}
		}
	}
	int cnt = 0;
	for (int i=0; i<N; i++) {
		if (dsu.Find(i) == i) cnt ++;
	}
	if (cnt != 1) return 0;
	vector<int> U, V, A, B;
	for (auto &[u, v] : edge) {
		U.push_back(u);
		V.push_back(v);
		if (x[u] == x[v]) {
			B.push_back((y[u] + y[v]) / 2);
			if ((x[u] + 1 + B.back()) % 4 == 2) A.push_back(x[u] + 1);
			else A.push_back(x[u] - 1);
		}
		else {
			A.push_back((x[u] + x[v]) / 2);
			if ((y[u] + 1 + A.back()) % 4 == 0) B.push_back(y[u] + 1);
			else B.push_back(y[u] - 1);
		}
	}
	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