Submission #1242678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242678		franuch	Fountain Parks (IOI21_parks)	C++20	0 / 100	28 ms	8636 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back

ll cnt;
vc<ll> par, rnk;
void init(ll n) {
	cnt = n;
	par.assign(n, -1);
	rnk.assign(n, -1);
}
ll find(ll v) {
	if (par[v] == -1)
		return v;
	par[v] = find(par[v]);
	return par[v];
}
void onion(ll v, ll w) {
	ll x = find(v);
	ll y = find(w);
	if (x == y)
		return;
	cnt--;
	if (rnk[x] < rnk[y])
		par[x] = y;
	else if (rnk[y] < rnk[x])
		par[y] = x;
	else {
		par[x] = y;
		rnk[y]++;
	}
}

ll construct_roads(std::vc<ll> x, std::vc<ll> y) {
	ll N = 100'000;
	ll n = sz(x);
	vc<vc<ll>> grid(3, vc<ll>(N, -1));
	for (ll i = 0; i < n; i++)
		grid[x[i] / 2 - 1][y[i] / 2 - 1] = i;
	
	init(n);
	vc<ll> ru, rv, rx, ry;
	for (ll j = 0; j < 3; j++)
		for (ll i = 0; i + 1 < n; i++) {
			ll u = grid[j][i], v = grid[j][i + 1];
			if (u != -1 and v != -1 and find(u) != find(v)) {
				onion(u, v);
				ru.pub(u);
				rv.pub(v);
				if (j == 0)
					rx.pub(1);
				else if (j == 1 and i % 2 == 1)
					rx.pub(3);
				else if (j == 1)
					rx.pub(5);
				else
					rx.pub(7);
				ry.pub(y[u] + 1);
			}
		}
	for (ll i = 0; i < N; i++) {
		ll u = grid[0][i], v = grid[1][i];
		if (u != -1 and v != -1 and find(u) != find(v)) {
			onion(u, v);
			ru.pub(u);
			rv.pub(v);
			rx.pub(3);
			if (i % 2 == 0)
				ry.pub(y[u] + 1);
			else
				ry.pub(y[u] - 1);
		}
		u = grid[1][i], v = grid[2][i];
		if (u != -1 and v != -1 and find(u) != find(v)) {
			onion(u, v);
			ru.pub(u);
			rv.pub(v);
			rx.pub(5);
			if (i % 2 == 1)
				ry.pub(y[u] + 1);
			else
				ry.pub(y[u] - 1);
		}
	}
	if (cnt > 1)
		return 0;
	build(ru, rv, rx, ry);
	return 1;
}

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