Submission #570492

#	Time	Username	Problem	Language	Result	Execution time	Memory
570492		8e7	Fountain Parks (IOI21_parks)	C++17	30 / 100	284 ms	67056 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<pii> > adj;
unordered_map<ll, bool> vis;
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, ll prv) {
	vis[n] = 1;
	for (auto p:adj[n]) {
		if (p.ff != prv) {
			u.push_back(p.ss / maxn);
			v.push_back(p.ss % maxn);
			a.push_back(n / maxn);
			b.push_back(n % maxn);
			if (!vis[p.ff]) dfs(p.ff, n);
		}
	}
}
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});
	}

	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 (i == 4) continue;
			if (xv[i][j].ff + 2 == xv[i][j+1].ff) {
				dsu.Union(xv[i][j].ss, xv[i][j+1].ss);
				u.push_back(xv[i][j].ss);
				v.push_back(xv[i][j+1].ss);
				b.push_back(xv[i][j].ff + 1);
				if (i == 2) a.push_back(1);
				else a.push_back(7);
			}
		}
		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);
				ll ind = h(yv[i][j].ss, yv[i][j+1].ss), v1 = h(yv[i][j].ff + 1, i-1), v2 = h(yv[i][j].ff + 1, i+1);
				adj[v1].push_back({v2, ind});
				adj[v2].push_back({v1, ind});
			}
		}
	}
	{
		int i = 4;
		for (int j = 0;j < (int)xv[i].size() - 1;j++) {
			if (xv[i][j].ff + 2 == xv[i][j+1].ff) {
				if (dsu.find(xv[i][j].ss) == dsu.find(xv[i][j+1].ss)) continue;
				dsu.Union(xv[i][j].ss, xv[i][j+1].ss);
				ll ind = h(xv[i][j].ss, xv[i][j+1].ss), v1 = h(i-1, xv[i][j].ff + 1), v2 = h(i+1, xv[i][j].ff + 1);
				adj[v1].push_back({v2, ind});
				adj[v2].push_back({v1, ind});
			}
		}
	}
	if (dsu.merges != n - 1) return 0;
	for (auto i:adj) {
		if (i.ss.size() == 1 && !vis[i.ff]) dfs(i.ff, -1);
	}
	for (auto i:adj) {
		if (!vis[i.ff]) dfs(i.ff, i.ss[0].ff);
	}
	build(u, v, a, b);
	return 1;
}

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