Submission #435577

#	Time	Username	Problem	Language	Result	Execution time	Memory
435577		grt	Fountain Parks (IOI21_parks)	C++17	55 / 100	929 ms	126824 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 800 * 1000 + 10;
map<pi, int>fontain;
pi road[nax];
int n;
vi V[nax], V2[nax];
map<pi, int>pts;
pi inv[nax];
bool vis[nax];
int match[nax];

bool augument(int u) {
	vis[u] = true;
	for(int v : V[u]) {
		if(match[v] == -1) {
			match[u] = v;
			match[v] = u;
			return true;
		}
	}
	for(int v : V[u]) {
		if(!vis[match[v]] && augument(match[v])) {
			match[u] = v;
			match[v] = u;
			return true;
		}
	}
	return false;
}

void dfs(int x) {
	vis[x] = true;
	for(int nbh : V2[x]) if(!vis[nbh]) {
		dfs(nbh);
	}
}

int construct_roads(vi xx, vi yx) {
	for(int i = 0; i < (int)xx.size(); ++i) {
		fontain[{xx[i], yx[i]}] = i;
	}
	for(auto it : fontain) {
		auto [x, y] = it.ST;
		if(fontain.count({x + 2, y})) {
			road[n] = {it.ND, fontain[{x + 2, y}]};
			pts[{x + 1, y - 1}];
			pts[{x + 1, y + 1}];
			n++;
		}
		if(fontain.count({x, y + 2})) {
			road[n] = {it.ND, fontain[{x, y + 2}]};
			pts[{x - 1, y + 1}];
			pts[{x + 1, y + 1}];
			n++;
		}
	}
	int id = 0;
	for(auto &it : pts) {
		inv[id] = it.ST;
		it.ND = id++;
	}
	for(int i = 0; i < n; ++i) {
		V2[road[i].ST].PB(road[i].ND);
		V2[road[i].ND].PB(road[i].ST);
		int x1 = xx[road[i].ST], y1 = yx[road[i].ST];
		int x2 = xx[road[i].ND], y2 = yx[road[i].ND];
		if(x1 == x2) {
			int y = (y1 + y2) / 2;
			for(int x : {x1 - 1, x1 + 1}) {
				int nr = pts[{x, y}];
				V[i].emplace_back(n + nr);
				V[n + nr].emplace_back(i);
			}
		} else if(y1 == y2) {
			int x = (x1 + x2) / 2;
			for(int y : {y1 - 1, y1 + 1}) {
				int nr = pts[{x, y}];
				V[i].emplace_back(n + nr);
				V[n + nr].emplace_back(i);
			}
		}
	}
	dfs(0);
	for(int i = 0; i < (int)xx.size(); ++i) {
		if(!vis[i]) {
			return 0;
		}
	}
	for(int i = 0; i < n + id; ++i) {
		match[i] = -1;
	}
	while(true) {
		bool any = false;
		for(int i = 0; i < n + id; ++i) {
			vis[i] = false;
		}
		for(int i = 0; i < n + id; ++i) {
			if(match[i] == -1 && augument(i)) {
				any = true;
			}
		}
		if(!any) break;
	}
	for(int i = 0; i < n; ++i) {
		if(match[i] == -1) {
			return 0;
		}
	}
	vi u(n), v(n), a(n), b(n);
	for(int i = 0; i < n; ++i) {
		u[i] = road[i].ST;
		v[i] = road[i].ND;
		a[i] = inv[match[i] - n].ST;
		b[i] = inv[match[i] - n].ND;
	}
	build(u,v,a,b);
	return 1;
}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(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