Submission #827113

#	Time	Username	Problem	Language	Result	Execution time	Memory
827113		ymm	Fountain Parks (IOI21_parks)	C++17	70 / 100	3101 ms	79292 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 200'010;

namespace dsu {
	int par[N];
	void init(int n) { memset(par, -1, sizeof(*par)*n); }
	int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
	bool unite(int v, int u) {
		v = rt(v);
		u = rt(u);
		if (v == u)
			return 0;
		par[u] = v;
		return 1;
	}
}

map<pii,int> pts;
vector<pii> edge;
vector<int> X, Y;
int n;

int get_pnt(int x, int y)
{
	auto it = pts.find(pii(x, y));
	return it == pts.end()? -1: it->second;
}

tuple<int,int,int,int> get_chair(int p1, int p2)
{
	int x1 = X[p1], y1 = Y[p1], x2 = X[p2], y2 = Y[p2];
	if (x1 == x2)
		return {x1-1, (y1+y2)/2, x1+1, (y1+y2)/2};
	else
		return {(x1+x2)/2, y1-1, (x1+x2)/2, y1+1};
}

namespace matching {
	int match[3*N];
	int par[3*N];
	vector<int> A[3*N];
	vector<pii> chairs;

	bool bfs(int s)
	{
		vector<int> q = {s}, q2;
		par[s] = -2;
		int vv;
		Loop (i,0,q.size()) {
			int v = q[i];
			//cerr << "bfs " << v << '\n';
			for (int u : A[v]) {
				if (par[u] != -1)
					continue;
				par[u] = v;
				q2.push_back(u);
				if (match[u] == -1) {
					vv = u;
					goto found;
				}
				int u2 = match[u];
				par[u2] = u;
				q.push_back(u2);
			}
		}
		return 0;
	found:
		while (vv != -2) {
			match[vv] = par[vv];
			match[par[vv]] = vv;
			vv = par[par[vv]];
		}
		for (int x : q2)
			par[x] = -1;
		return 1;
	}

	vector<pii> get_match(vector<pii> e) {
		int m = e.size();
		chairs.clear();
		Loop (i,0,m) {
			auto [p1, p2] = e[i];
			auto [x1, y1, x2, y2] = get_chair(p1, p2);
			chairs.emplace_back(x1, y1);
			chairs.emplace_back(x2, y2);
		}
		sort(chairs.begin(), chairs.end());
		chairs.resize(unique(chairs.begin(), chairs.end()) - chairs.begin());
		//for (auto [x, y] : chairs)
		//	cerr << x << ' ' << y << '\n';
		Loop (i,0,m+chairs.size()) {
			A[i].clear();
			match[i] = -1;
			par[i] = -1;
		}
		Loop (i,0,m) {
			auto [p1, p2] = e[i];
			auto [x1, y1, x2, y2] = get_chair(p1, p2);
			int c1 = lower_bound(chairs.begin(), chairs.end(), pii(x1, y1)) - chairs.begin();
			int c2 = lower_bound(chairs.begin(), chairs.end(), pii(x2, y2)) - chairs.begin();
			A[i].push_back(m+c1);
			A[i].push_back(m+c2);
			A[m+c1].push_back(i);
			A[m+c2].push_back(i);
		}
		Loop (i,0,m) {
			//cerr << "try " << i << '\n';
			if (!bfs(i))
				return {};
			//Loop (i,0,m+chairs.size())
			//	cerr << match[i] << ' ';
			//cerr << '\n';
		}
		//cerr << "all good!\n";
		vector<pii> ans;
		Loop (i,0,m) {
			int c = match[i]-m;
			ans.emplace_back(chairs[c].first, chairs[c].second);
		}
		return ans;
	}
}

void make_edges()
{
	set<pii> black;
	Loop (i,0,n) {
		int x = X[i];
		int y = Y[i];
		if (get_pnt(x, y+2) != -1 && get_pnt(x+2, y) != -1 && get_pnt(x+2, y+2) != -1)
			black.insert({x+1, y+1});
	}
	vector<pii> e1, e2;
	Loop (i,0,n) {
		int x = X[i];
		int y = Y[i];
		int p1 = get_pnt(x, y+2);
		if (p1 == -1)
			continue;
		auto [c1x, c1y, c2x, c2y] = get_chair(i, p1);
		if (black.count(pii(c1x, c1y)) + black.count(pii(c2x, c2y)) == 1)
			e1.push_back({i, p1});
		else
			e2.push_back({i, p1});
	}
	Loop (i,0,n) {
		int x = X[i];
		int y = Y[i];
		int p1 = get_pnt(x+2, y);
		if (p1 == -1)
			continue;
		auto [c1x, c1y, c2x, c2y] = get_chair(i, p1);
		if (black.count(pii(c1x, c1y)) + black.count(pii(c2x, c2y)) == 1)
			e1.push_back({i, p1});
		else
			e2.push_back({i, p1});
	}
	edge = e1;
	edge.insert(edge.end(), e2.begin(), e2.end());
}

int construct_roads(std::vector<int> _X, std::vector<int> _Y) {
	X = _X; Y = _Y;
	n = X.size();
	if (n == 1) {
		build({}, {}, {}, {});
		return 1;
	}
	Loop (i,0,n)
		pts[pii(X[i], Y[i])] = i;
	make_edges();
	//for (auto [x, y] : edge)
	//	cerr << X[x] << ' ' << Y[x] << " - " << X[y] << ' ' << Y[y] << '\n';
	mt19937_64 rd(time(0));
	while (clock() < 3*CLOCKS_PER_SEC) {
		dsu::init(n);
		int cnt = 0;
		vector<pii> e;
		for (auto [x, y] : edge) {
			if (dsu::unite(x, y)) {
				e.emplace_back(x, y);
				++cnt;
			}
		}
		if (cnt != n-1)
			return 0;
		auto chairs = matching::get_match(e);
		//cerr << "found!\n";
		//for (auto [x, y] : chairs)
		//	cerr << x << ' ' << y << '\n';
		if (chairs.empty())
			continue;
		vector<int> ex, ey, cx, cy;
		Loop (i,0,n-1) {
			ex.push_back(e[i].first);
			ey.push_back(e[i].second);
			cx.push_back(chairs[i].first);
			cy.push_back(chairs[i].second);
		}
		build(ex, ey, cx, cy);
		return 1;
	}
	return 0;
}

Compilation message (stderr)

parks.cpp: In function 'bool matching::bfs(int)':
parks.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
parks.cpp:55:3: note: in expansion of macro 'Loop'
   55 |   Loop (i,0,q.size()) {
      |   ^~~~
parks.cpp: In function 'std::vector<std::pair<int, int> > matching::get_match(std::vector<std::pair<int, int> >)':
parks.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
parks.cpp:97:3: note: in expansion of macro 'Loop'
   97 |   Loop (i,0,m+chairs.size()) {
      |   ^~~~

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