Submission #1198580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198580		Nonoze	Fountain Parks (IOI21_parks)	C++20	70 / 100	994 ms	97316 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)x.size()
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)

int ret(vector<pair<int, int>> vec1, vector<pair<int, int>> vec2) {
	vector<int> a, b, c, d;
	for (auto &[x, y]: vec1) a.pb(x), b.pb(y);
	for (auto &[x, y]: vec2) c.pb(x), d.pb(y);
	build(a, b, c, d);
	return 1;
}

int n;


int construct_roads(vector<int> x, vector<int> y) {
	n=sz(x);
	map<pair<int, int>, int> mp; for (int i=0; i<n; i++) mp[{x[i], y[i]}]=i;
	vector<pair<int, int>> bridges;
	vector<bool> vis(n, 0); vis[0]=1;
	queue<int> q; q.push(0);
	while (!q.empty()) {
		int i=q.front(); q.pop();
		if (mp.count({x[i]+2, y[i]}) && !vis[mp[{x[i]+2, y[i]}]]) {
			int j=mp[{x[i]+2, y[i]}];
			vis[j]=1;
			bridges.pb({i, j});
			q.push(j);
		}
		if (mp.count({x[i]-2, y[i]}) && !vis[mp[{x[i]-2, y[i]}]]) {
			int j=mp[{x[i]-2, y[i]}];
			vis[j]=1;
			bridges.pb({i, j});
			q.push(j);
		}
		if (mp.count({x[i], y[i]+2}) && !vis[mp[{x[i], y[i]+2}]]) {
			int j=mp[{x[i], y[i]+2}];
			vis[j]=1;
			bridges.pb({i, j});
			q.push(j);
		}
		if (mp.count({x[i], y[i]-2}) && !vis[mp[{x[i], y[i]-2}]]) {
			int j=mp[{x[i], y[i]-2}];
			vis[j]=1;
			bridges.pb({i, j});
			q.push(j);
		}
	}
	for (int i=0; i<n; i++) if (!vis[i]) return 0;
	assert(sz(bridges)==n-1);
	map<pair<int, int>, vector<int>> mpp;
	vector<vector<pair<int, int>>> can;
	for (int i=0; i<n-1; i++) {
		int a=x[bridges[i].fi], b=y[bridges[i].fi], u=x[bridges[i].se], v=y[bridges[i].se]; can.pb({});
		if (a==u) {
			mpp[{a-1, (b+v)/2}].pb(i);
			mpp[{a+1, (b+v)/2}].pb(i);
			can.back().pb({a-1, (b+v)/2});
			can.back().pb({a+1, (b+v)/2});
		} else {
			mpp[{(a+u)/2, b-1}].pb(i);
			mpp[{(a+u)/2, b+1}].pb(i);
			can.back().pb({(a+u)/2, b-1});
			can.back().pb({(a+u)/2, b+1});
		}
	}
	set<pair<int, int>> already;
	vector<int> pos(n-1, 2);
	set<pair<int, int>> st; for (int i=0; i<n-1; i++) st.insert({2, i});
	vector<pair<int, int>> empls(n-1);
	while (!st.empty()) {
		auto i=st.begin()->se; st.erase(st.begin());
		if (already.count(can[i][0])) swap(can[i][0], can[i][1]);
		if (!already.count(can[i][1])) {
			int nb1=0, nb2=0;
			for (auto &u: mpp[can[i][0]]) if (st.count({pos[u], u})) {
				if (pos[u]==1) nb1=100000000;
				nb1++;
			}
			for (auto &u: mpp[can[i][1]]) if (st.count({pos[u], u})) {
				if (pos[u]==1) nb2=100000000;
				nb2++;
			}
			if (nb2<nb1) swap(can[i][0], can[i][1]);
		}
		already.insert(can[i][0]);
		empls[i]=can[i][0];
		for (auto &u: mpp[can[i][0]]) if (st.count({pos[u], u})) {
			st.erase({pos[u], u});
			pos[u]--;
			assert(pos[u]>0);
			st.insert({pos[u], u});
		}
	}

	return ret(bridges, empls);
}

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