제출 #1242728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242728		franuch	Fountain Parks (IOI21_parks)	C++20	45 / 100	240 ms	33196 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 = sz(x);
	ll N = 200'001;
	vc<map<ll, ll>> c(N);
	for (ll i = 0; i < n; i++)
		c[x[i]][y[i]] = i;
	
	init(n);
	vc<ll> ru(n - 1), rv(n - 1), rx(n - 1), ry(n - 1);
	ll j = 0;
	for (ll u = 0; u < n; u++) {
		vc<ll> ox = {2, 0};
		vc<ll> oy = {0, 2};
		for (ll i = 0; i < 2; i++) {
			ll vx = x[u] + ox[i];
			ll vy = y[u] + oy[i];
			if (c[vx].find(vy) == c[vx].end())
				continue;
			ll v = c[vx][vy];
			if (find(u) == find(v))
				continue;
			onion(u, v);
			ru[j] = u;
			rv[j] = v;
			if (i == 0) {
				rx[j] = vx - 1;
				if ((vx + vy) / 2 % 2 == 1)
					ry[j] = vy + 1;
				else
					ry[j] = vy - 1;
			} else {
				if ((vx + vy) / 2 % 2 == 0)
					rx[j] = vx + 1;
				else
					rx[j] = vx - 1;
				ry[j] = vy - 1;
			}
			j++;
		}
	}
	if (j < n - 1)
		return 0;
	build(ru, rv, rx, ry);
	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