Submission #446645

#	Time	Username	Problem	Language	Result	Execution time	Memory
446645		LucaDantas	Fountain Parks (IOI21_parks)	C++17	70 / 100	1761 ms	186464 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '['; string sep = ""; for (const auto &x : v) os << sep << x, sep = ", "; return os << ']'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, const set<A> &s) { os << '{'; string sep = ""; for (const auto &x : s) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const map<A, B> &m) { os << '{'; string sep = ""; for (const auto &x : m) os << sep << x.first << " -> " << x.second, sep = ", "; return os << '}'; }

void debug() { cerr << endl; }
template<typename Ini, typename... Fim> void debug(Ini I, Fim... F) { cerr << I; if(sizeof...(F)) cerr << ", "; debug(F...);}
#define db(...) cerr << "DEBUG (" << #__VA_ARGS__ << ") == ", debug(__VA_ARGS__)

#define pb push_back
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),(a).end()
#define ff first
#define ss second

constexpr int inf = 0x3f3f3f3f;
constexpr int maxn = 8e5 + 10;

mt19937 rng(random_device{}());

int rnd(int x) { return (rng() % x + x) % x; }

vector<int> g[maxn];

int match[maxn];
bool mark[maxn];

int t, n, qtd_ruas;

bool dfs(int u) {
	mark[u] = 1;
	if(u >= qtd_ruas) return (match[u] == -1 ? 1 : dfs(match[u]));

	for(int v : g[u]) {
		if(mark[v] || !dfs(v)) continue;
		match[u] = v; match[v] = u;
		return 1;
	}

	return 0;
}

struct Road { // todas as ruas possiveis
	int x, y, tipo; // ponto inicial da rua e se é vertical ou horizontal
} ruas[maxn];

pii conecta[maxn];

struct Banco {
	int x, y;
} bancos[maxn];

map<pair<int,int>, int> mp; // salva o id dos pontos

inline void add(int a, int b) { g[a].pb(b), g[b].pb(a); }

int get(pii p) { 
	if(mp.count(p)) return mp[p];
	bancos[t] = {p.ff, p.ss};
	return mp[p] = t++;
}

bool mark2[maxn];
int vis = 0;

void vai(int x, int y) {
	++vis;
	int id = mp[pii(x, y)];
	mark2[id] = 1;
	vector<int> gld(4); iota(all(gld), 0); shuffle(all(gld), rng);
	for(int opa : gld) {
		if(opa == 0 && mp.count({x+2, y}) && !mark2[mp[pii(x+2, y)]]) {
			conecta[t] = {id, mp[pii(x+2, y)]};
			ruas[t++] = {x, y, 0};
			// db(x, y, x+2, y);
			vai(x+2, y);
		}
		if(opa == 1 && mp.count({x-2, y}) && !mark2[mp[pii(x-2, y)]]) {
			conecta[t] = {mp[pii(x-2, y)], id};
			ruas[t++] = {x-2, y, 0};
			// db(x, y, x-2, y);
			vai(x-2, y);
		}
		if(opa == 2 && mp.count({x, y+2}) && !mark2[mp[pii(x, y+2)]]) {
			conecta[t] = {id, mp[pii(x, y+2)]};
			ruas[t++] = {x, y, 1};
			// db(x, y, x, y+2);
			vai(x, y+2);
		}
		if(opa == 3 && mp.count({x, y-2}) && !mark2[mp[pii(x, y-2)]]) {
			conecta[t] = {mp[pii(x, y-2)], id};
			ruas[t++] = {x, y-2, 1};
			// db(x, y, x, y-2);
			vai(x, y-2);
		}
	}
}

int bonitao(vector<int> x, vector<int> y) {
	mp.clear(); vis = t = n = qtd_ruas = 0;
	memset(bancos, 0, sizeof bancos);
	memset(mark, 0, sizeof mark);
	memset(mark2, 0, sizeof mark2);
	memset(match, 0, sizeof match);
	for(int i = 0; i < maxn; i++)
		g[i].clear(), conecta[i] = {0, 0};
	n = sz(x);
	for(int i = 0; i < n; i++)
		mp[pii(x[i], y[i])] = i;
	int hm = rnd(n);
	vai(x[hm], y[hm]);
	if(vis != n) return -1; // impossivel, o grafo completo não é conexo
	
	qtd_ruas = t;
	for(int i = 0; i < qtd_ruas; i++) {
		auto [X, Y, tipo] = ruas[i];
		if(!tipo) {
			int aq = get({X+1, Y+1});
			add(i, aq);

			aq = get({X+1, Y-1});
			add(i, aq);
		} else {
			int aq = get({X+1, Y+1});
			add(i, aq);

			aq = get({X-1, Y+1});
			add(i, aq);
		}
	}

	int ans = 0;
	memset(match, -1, sizeof match);

	vector<int> p(qtd_ruas); iota(all(p), 0);

	for(int i = 0; i < t; i++)
		shuffle(all(g[i]), rng);

	for(int antes = -1; ans != antes;) {
		antes = ans;
		memset(mark, 0, sizeof mark);
		shuffle(all(p), rng);
		for(int i = 0; i < qtd_ruas; i++)
			if(!mark[p[i]] && match[p[i]] == -1 && dfs(p[i])) ++ans;
	}

	if(ans != qtd_ruas) return 0;
	
	vector<int> u(qtd_ruas), v(qtd_ruas), a(qtd_ruas), b(qtd_ruas);

	for(int i = 0; i < qtd_ruas; i++) {
		u[i] = conecta[i].ff, v[i] = conecta[i].ss;
		a[i] = bancos[match[i]].x, b[i] = bancos[match[i]].y;
	}
	build(u, v, a, b);
	return 1;
}

int construct_roads(vector<int> x, vector<int> y) {
	for(int i = 0; i < 2; i++) {
		int a = bonitao(x, y);
		if(a == -1) return 0;
		if(a == 0) continue;
		return 1;
	}
	assert(0);
	return 0;
}

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