Submission #570794

#	Time	Username	Problem	Language	Result	Execution time	Memory
570794		8e7	Fountain Parks (IOI21_parks)	C++17	100 / 100	749 ms	99060 KiB

parks

//Challenge: Accepted
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<ll, ll>
#define ff first
#define ss second
vector<pii> xv[maxn], yv[maxn];
unordered_map<ll, vector<ll> > g;
unordered_set<ll> bad;
unordered_map<ll, bool> vis;
vector<ll> outside;
ll h(int x, int y) {
	return (ll)x * maxn + y;
}

struct DSU{
	int par[maxn];
	int merges = 0;
	void init(int n) {
		for (int i = 0;i < n;i++) par[i] = i;
	}
	int find(int a) {
		return a == par[a] ? a : (par[a] = find(par[a]));
	}
	void Union(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return;
		merges++;
		par[a] = b;
	}
} dsu;
vector<int> u, v, a, b;
void dfs(ll n) {
	vis[n] = 1;
	for (auto p:g[n]) {
		if (!vis[p]) {
			int vx = (p / maxn + n / maxn) / 2, vy = (p % maxn + n % maxn) / 2;
			bad.insert(h(vx, vy));
			dfs(p);
		}
	}
}

unordered_set<ll> vert, block;
int construct_roads(std::vector<int> X, std::vector<int> Y) {
	int n = X.size();
	dsu.init(n);
	for (int i = 0;i < n;i++) {
		xv[X[i]].push_back({Y[i], i});
		yv[Y[i]].push_back({X[i], i});
		vert.insert(h(X[i], Y[i]));
	}
	auto found = [&] (int x, int y){
		return vert.find(h(x, y)) != vert.end();
	};
	for (auto i:vert) {
		int x = i / maxn, y = i % maxn;
		if (found(x+2, y) && found(x+2, y+2) && found(x, y+2)) {
			block.insert(h(x+1, y+1));
		}
	}
	for (auto i:block) {
		int x = i / maxn, y = i % maxn;
		if ((x + y) % 4) {
			g[h(x+2, y)].push_back(i);	
			g[h(x-2, y)].push_back(i);
			if (block.find(h(x+2, y)) == block.end()) {
				outside.push_back(h(x+2, y));	
			}
			if (block.find(h(x-2, y)) == block.end()) {
				outside.push_back(h(x-2, y));	
			}
		} else {
			g[h(x, y+2)].push_back(i);	
			g[h(x, y-2)].push_back(i);
			if (block.find(h(x, y+2)) == block.end()) {
				outside.push_back(h(x, y+2));	
			}
			if (block.find(h(x, y-2)) == block.end()) {
				outside.push_back(h(x, y-2));	
			}
		}
	}
	for (auto i:outside) dfs(i);
	for (int i = 0;i < maxn;i += 2) {
		sort(xv[i].begin(), xv[i].end());
		sort(yv[i].begin(), yv[i].end());
		for (int j = 0;j < (int)xv[i].size() - 1;j++) {
			if (xv[i][j].ff + 2 == xv[i][j+1].ff) {
				dsu.Union(xv[i][j].ss, xv[i][j+1].ss);
				if (bad.find(h(i, xv[i][j].ff + 1)) != bad.end()) continue;
				u.push_back(xv[i][j].ss);
				v.push_back(xv[i][j+1].ss);
				b.push_back(xv[i][j].ff + 1);	
				if ((xv[i][j].ff + i + 2) % 4) {
					a.push_back(i+1);
				} else {
					a.push_back(i-1);
				}
			}
		}
		for (int j = 0;j < (int)yv[i].size() - 1;j++) {
			if (yv[i][j].ff + 2 == yv[i][j+1].ff) {
				dsu.Union(yv[i][j].ss, yv[i][j+1].ss);
				if (bad.find(h(yv[i][j].ff + 1, i)) != bad.end()) continue;
				u.push_back(yv[i][j].ss);
				v.push_back(yv[i][j+1].ss);
				a.push_back(yv[i][j].ff + 1);	
				if ((yv[i][j].ff + i) % 4) {
					b.push_back(i+1);
				} else {
					b.push_back(i-1);
				}
			}
		}
	}
	if (dsu.merges != n - 1) return 0;
	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