Submission #435590

#	Time	Username	Problem	Language	Result	Execution time	Memory
435590		PinkRabbit	Fountain Parks (IOI21_parks)	C++17	55 / 100	959 ms	109156 KiB

parks

// PinkRabbit

#include "parks.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <ctime>
#include <random>
#include <chrono>

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
inline T range(T l, T r) {
	return std::uniform_int_distribution<T>(l, r)(rng);
}

template<typename T>
inline void vec2arr(std::vector<T> v, T *arr, T bias = 0) {
	int n = (int)v.size();
	for (int i = 1; i <= n; ++i)
		arr[i] = v[i - 1] + bias;
}
template<typename T>
inline std::vector<T> arr2vec(T *arr, int n, T bias = 0) {
	std::vector<T> v(n);
	for (int i = 1; i <= n; ++i)
		v[i - 1] = arr[i] + bias;
	return v;
}

typedef std::vector<int> VI;
const int MN = 800005;
const int MV = 400005;

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

int N;
int x[MN], y[MN];
int ndir[MN][4], edir[MN][4];
std::map<int, int> mp[MV];
int eu[MN * 2], ev[MN * 2], M;

int per[MN * 2], iper[MN * 2];
int AnsU[MN], AnsV[MN], AnsA[MN], AnsB[MN];
int pa[MN];
int fp(int u) {
	return pa[u] ? pa[u] = fp(pa[u]) : u;
}
inline bool GenTree() {
	int tot = 0;
	std::shuffle(per + 1, per + M + 1, rng);
	for (int i = 1; i <= M; ++i)
		iper[i] = 0;
	for (int id = 1; id <= M; ++id) {
		int u = eu[per[id]], v = ev[per[id]];
		int pu = fp(u), pv = fp(v);
		if (pu != pv) {
			++tot;
			AnsU[tot] = u;
			AnsV[tot] = v;
			pa[pu] = pv;
			iper[per[id]] = tot;
		}
	}
	return tot == N - 1;
}

VI G[MN];
int bel[MN], scnt;
int dfn[MN], low[MN], dfc;
int stk[MN], top;
bool instk[MN];
void Tarjan(int u) {
	dfn[u] = low[u] = ++dfc;
	instk[stk[++top] = u] = true;
	for (int v : G[u]) {
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = std::min(low[u], low[v]);
		} else if (instk[v])
			low[u] = std::min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u]) {
		++scnt;
		while (true) {
			int w = stk[top--];
			instk[w] = false;
			bel[w] = scnt;
//			printf("bel[%d] = %d\n", w, scnt);
			if (w == u)
				break;
		}
	}
}
inline bool Solve() {
	for (int i = 1; i <= 2 * (N - 1); ++i)
		G[i].clear(), dfn[i] = low[i] = 0;
	auto AddE = [&](int u, int tu, int v, int tv) -> void {
		if (!u || !v || !iper[u] || !iper[v])
			return ;
//		printf("([(%d, %d) - (%d, %d)], %d) <---> ([(%d, %d) - (%d, %d)], %d)\n", 2 * x[eu[u]], 2 * y[eu[u]], 2 * x[ev[u]], 2 * y[ev[u]], tu, 2 * x[eu[v]], 2 * y[eu[v]], 2 * x[ev[v]], 2 * y[ev[v]], tv);
		u = iper[u], v = iper[v];
		G[u + (tu ? N - 1 : 0)].push_back(v + (tv ? 0 : N - 1));
		G[v + (tv ? N - 1 : 0)].push_back(u + (tu ? 0 : N - 1));
	};
	for (int i = 1; i <= N; ++i) {
		AddE(edir[i][0], 1, edir[i][1], 1);
		AddE(edir[i][1], 0, edir[i][2], 1);
		AddE(edir[i][2], 0, edir[i][3], 0);
		AddE(edir[i][3], 1, edir[i][0], 0);
		if (ndir[i][0] && ndir[i][1] && ndir[ndir[i][0]][1]) {
			AddE(edir[i][0], 1, edir[ndir[i][1]][0], 0);
			AddE(edir[i][1], 1, edir[ndir[i][0]][1], 0);
		}
	}
	scnt = 0;
	for (int u = 1; u <= 2 * (N - 1); ++u)
		if (!dfn[u])
			Tarjan(u);
	for (int i = 1; i <= N - 1; ++i) {
		if (bel[i] == bel[i + N - 1])
			return false;
		int d = bel[i + N - 1] < bel[i];
		AnsA[i] = x[AnsU[i]] + x[AnsV[i]];
		AnsB[i] = y[AnsU[i]] + y[AnsV[i]];
		if (x[AnsU[i]] == x[AnsV[i]])
			AnsA[i] += (d ? 1 : -1);
		if (y[AnsU[i]] == y[AnsV[i]])
			AnsB[i] += (d ? 1 : -1);
	}
	build(arr2vec(AnsU, N - 1, -1), arr2vec(AnsV, N - 1, -1), arr2vec(AnsA, N - 1), arr2vec(AnsB, N - 1));
	return true;
}

int construct_roads(VI t_x, VI t_y) {
	clock_t tstart = clock();
	N = (int)t_x.size();
	vec2arr(t_x, x);
	vec2arr(t_y, y);
	for (int i = 1; i <= N; ++i) {
		x[i] /= 2;
		y[i] /= 2;
		mp[x[i]][y[i]] = i;
	}
	for (int i = 1; i <= N; ++i) {
		for (int d = 0; d < 2; ++d) {
			int nx = x[i] + dx[d];
			int ny = y[i] + dy[d];
			auto it = mp[nx].find(ny);
			if (it != mp[nx].end()) {
				++M;
				eu[M] = i;
				ev[M] = it -> second;
				if (rng() & 1)
					std::swap(eu[M], ev[M]);
				ndir[i][d] = it->second;
				ndir[it->second][d ^ 2] = i;
				edir[i][d] = M;
				edir[it->second][d ^ 2] = M;
			}
		}
	}
	for (int i = 1; i <= M; ++i)
		per[i] = i;
	if (!GenTree())
		return 0;
	if (Solve())
		return 1;
	while ((clock() - tstart) / (double)CLOCKS_PER_SEC < 2.7) {
		GenTree();
		if (Solve())
			return 1;
	}
	return 0;
}

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