Submission #438128

#	Time	Username	Problem	Language	Result	Execution time	Memory
438128		gs14004	Fountain Parks (IOI21_parks)	C++17	70 / 100	727 ms	80620 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
const int MAXN = 400005;
const int mod = 1e9 + 7;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct point{
	int x, y, idx;
};

struct disj{
	int pa[MAXN];
	void init(int n){
		iota(pa, pa + n, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;

bool vis[MAXN];
int V = 0, E = 0;
vector<int> dfn;
vector<pi> gph[MAXN];

void dfs(int x){
	if(vis[x]) return;
	vis[x] = 1;
	dfn.push_back(x);
	V += 1;
	E += sz(gph[x]);
	for(auto &[_, y] : gph[x]) dfs(y);
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
	int n = sz(x);
	vector<point> p;
	vector<pi> edges;
	vector<pi> matches;
	vector<pi> to_mst;
	auto get_mode = [&](pi q){
		int x = q.first, y = q.second;
		int val = (p[y].x + p[y].y) % 4;
		if(val % 4 == 0) return p[x].x == p[y].x ? 0 : 2;
		return p[x].x == p[y].x ? 1 : 3;
	};
	for(int i = 0; i < n; i++){
		p.push_back({x[i], y[i], i});
	}
	sort(all(p), [&](const point &a, const point &b){
		return pi(a.x, a.y) < pi(b.x, b.y);
	});
	disj.init(n);
	for(int i = 1; i < sz(p); i++){
		if(p[i-1].x == p[i].x && p[i-1].y + 2 == p[i].y){
			to_mst.emplace_back(p[i-1].idx, p[i].idx);
		}
	}
	sort(all(p), [&](const point &a, const point &b){
		return pi(a.y, a.x) < pi(b.y, b.x);
	});
	for(int i = 1; i < sz(p); i++){
		if(p[i-1].y == p[i].y && p[i-1].x + 2 == p[i].x){
			to_mst.emplace_back(p[i-1].idx, p[i].idx);
		}
	}
	sort(all(p), [&](const point &a, const point &b){
		return a.idx < b.idx;
	});
	sort(all(to_mst), [&](const pi &x, const pi &y){
		return get_mode(x) < get_mode(y);
	});
	for(auto &[x, y] : to_mst){
		if(disj.uni(x, y)) edges.emplace_back(x, y);
	}
	if(sz(edges) != n - 1) return 0;
	map<pi, int> mp;
	vector<int> U, _V, A(n-1), B(n-1);
	for(auto &[x, y] : edges){
		U.push_back(x);
		_V.push_back(y);
		set<pi> s;
		int mx = (p[x].x + p[y].x) / 2;
		int my = (p[x].y + p[y].y) / 2;
		for(int i = 0; i < 4; i++){
			s.emplace(mx + dx[i], my + dy[i]);
		}
		s.erase(pi(p[x].x, p[x].y));
		s.erase(pi(p[y].x, p[y].y));
		for(auto &p : s){
			if(mp.find(p) == mp.end()){
				int idx = sz(mp);
				mp[p] = idx;
			}
		}
		matches.emplace_back(mp[*s.begin()], mp[*s.rbegin()]);
	}
	vector<int> deg(sz(mp));
	for(int i = 0; i < sz(matches); i++){
		int x, y; tie(x, y) = matches[i];
		gph[x].emplace_back(i, y);
		gph[y].emplace_back(i, x);
		deg[x]++;
		deg[y]++;
	}
	vector<pi> mrev(sz(mp));
	for(auto &[x, y] : mp){
		mrev[y] = x;
	}
	for(int i = 0; i < sz(mp); i++){
		if(!vis[i]){
			V = E = 0;
			dfn.clear();
			dfs(i);
			E /= 2;
			if(V < E){
				return 0;
			}
			assert(V >= E);
			queue<int> que;
			for(auto &v : dfn){
				if(deg[v] == 1){
					que.push(v);
				}
			}
			while(sz(que)){
				int x = que.front();
				que.pop();
				for(auto &[i, y] : gph[x]){
					if(!deg[y]) continue;
					deg[x]--;
					deg[y]--;
					A[i] = mrev[x].first;
					B[i] = mrev[x].second;
				//	printf("%d %d\n", i, x);
					if(deg[y] == 1){
						que.push(y);
					}
				}
			}
			if(V != E) continue;
			for(auto &v : dfn){
				if(deg[v] == 2){
					int I, V, W;
					for(auto &[i, w] : gph[v]){
						if(deg[w] == 2){
							deg[v]--;
							deg[w]--;
							tie(I, V, W) = make_tuple(i, v, w);
							break;
						}
					}
					gph[V].erase(find(all(gph[V]), pi(I, W)));
					gph[W].erase(find(all(gph[W]), pi(I, V)));
			//		printf("%d %d\n", I, W);
					A[I] = mrev[W].first;
					B[I] = mrev[W].second;
					que.push(V);
					break;
				}
			}
			while(sz(que)){
				int x = que.front();
				que.pop();
				for(auto &[i, y] : gph[x]){
					if(!deg[y]) continue;
					deg[x]--;
					deg[y]--;
			//		printf("%d %d\n", i, x);
					A[i] = mrev[x].first;
					B[i] = mrev[x].second;
					if(deg[y] == 1){
						que.push(y);
					}
				}
			}
		}
	}
	build(U, _V, A, B);
	return 1;
}

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