Submission #446628

#	Time	Username	Problem	Language	Result	Execution time	Memory
446628		LucaDantas	Fountain Parks (IOI21_parks)	C++17	55 / 100	1431 ms	126704 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{}());

struct DSU {
	int pai[maxn], peso[maxn], qtd;
	DSU() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
	int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
	void join(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return;
		--qtd;
		if(peso[a] < peso[b]) swap(a, b);
		pai[b] = a;
		peso[a] += peso[b];
	}
} dsu;

vector<int> pt[maxn], 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++;
}

int construct_roads(vector<int> x, vector<int> y) {
	n = sz(x); dsu.qtd = n;
	for(int i = 0; i < n; i++)
		mp[pii(x[i], y[i])] = i;
	for(int i = 0; i < n; i++) {
		if(mp.count({x[i]+2, y[i]})) {
			conecta[t] = {i, mp[pii(x[i]+2, y[i])]};
			ruas[t++] = {x[i], y[i], 0}; // 0 == horizontal
			dsu.join(i, mp[pii(x[i]+2, y[i])]);
		}
		if(mp.count({x[i], y[i]+2})) {
			conecta[t] = {i, mp[pii(x[i], y[i]+2)]};
			ruas[t++] = {x[i], y[i], 1}; // 1 == vertical
			dsu.join(i, mp[pii(x[i], y[i]+2)]);
		}
	}
	if(dsu.qtd != 1) return 0; // impossivel, o grafo completo não é conexo
	
	qtd_ruas = t;
	for(int i = 0; i < qtd_ruas; i++) {
		auto [X, Y, tipo] = ruas[i];
		// db(X, Y, tipo);
		if(!tipo) {
			int aq = get({X+1, Y+1});
			add(i, aq);
			
			// db(pii(X, Y), tipo, aq);

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

			aq = get({X-1, Y+1});
			add(i, aq);
			// db(pii(X, Y), tipo, 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;
		// db("OPA", ans, antes);
	}

	// db(ans);

	/* for(int i = 0; i < qtd_ruas; i++)
		db(i, match[i], bancos[match[i]].x, bancos[match[i]].y); */

	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;
}

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