Submission #831862

#	Time	Username	Problem	Language	Result	Execution time	Memory
831862		welleyth	Fountain Parks (IOI21_parks)	C++17	30 / 100	472 ms	57756 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int N = (int)3e5+11;

int p[N];

mt19937 rnd(time(nullptr));
int components;

int get(int x){
	return p[x] == x ? x : p[x] = get(p[x]);
}

void union_sets(int a,int b){
	a = get(a), b = get(b);
	if(a == b) return;
	if(rnd()&1) swap(a,b);
	p[a] = b;
	components--;
	return;
}

int construct_roads(std::vector<int> _x, std::vector<int> _y) {
	int n = _x.size();
	components = n;
	for(int i = 0; i < n; i++) p[i] = i;
	vector<pair<int,int>> fountains;
	map<pair<int,int>,int> id;
	for(int i = 0; i < n; i++){
		fountains.push_back(make_pair(_x[i],_y[i]));
		id[fountains.back()] = i;
	}
	sort(fountains.begin(),fountains.end());
	set<pair<int,int>> fountainPositions(fountains.begin(),fountains.end());

	vector<int> g[n];
	vector<pair<int,int>> edges;
	vector<pair<int,int>> coords;
	set<pair<int,int>> benches;
	// shuffle(fountains.begin(),fountains.end(),rnd);

	for(int mask = 0; mask < 1; mask++){
		for(auto&[x,y] : fountains){
			for(int i = -2; i <= 2; i += 2){
				// if((mask & 1) == 0 && i == 2) continue;
				for(int j = -2; j <= 2; j += 2){
					// if((mask >> 1 & 1) == 0 && j == 2) continue;
					if(abs(i) + abs(j) != 2) continue;
					int xn = x + i, yn = y + j;
					int id1 = id[make_pair(x,y)];
					if(!id.count(make_pair(xn,yn))) continue;
					int id2 = id[make_pair(xn,yn)];
					if(get(id1) != get(id2)){
						edges.push_back(make_pair(id1,id2));
						int a,b;
						if(x == xn){
							int my = (y+yn)/2;
							if(!benches.count({x-1,my}))
								a = x-1, b = my;
							else if(!benches.count({x+1,my}))
								a = x+1, b = my;
							else continue;
						} else {
							int mx = (x+xn)/2;
							if(!benches.count({mx,y-1}))
								a = mx, b = y-1;
							else if(!benches.count({mx,y+1}))
								a = mx, b = y+1;
							else continue;
						}
						// cerr << "from " << x << " " << y << ", to " << xn << " " << yn << "\n";
						// cerr << "a,b: " << a << " " << b << "\n";
						coords.push_back(make_pair(a,b));
						benches.insert(make_pair(a,b));
						union_sets(id1,id2);
					}
				}
			}
		}
	}
	
	if(components > 1) return 0;
	vector<int> x,y,a,b;
	for(size_t i = 0; i < edges.size(); i++){
		x.push_back(edges[i].first);
		y.push_back(edges[i].second);
		a.push_back(coords[i].first);
		b.push_back(coords[i].second);
	}
	build(x,y,a,b);
	return 1;
}

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