Submission #780640

#	Time	Username	Problem	Language	Result	Execution time	Memory
780640		raysh07	Fountain Parks (IOI21_parks)	C++17	100 / 100	543 ms	53964 KiB

parks

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

struct park{
	int x, y, i;
};

const int N = 2e5 + 69;
int root[N];

int find(int x){ 
	if (x == root[x]) return x;
	return root[x] = find(root[x]);
}

void unite(int x, int y){
	x = find(x); y = find(y);
	root[x] = y;
}

pair<int, int> f(int x, int y, int d){
	if (d == 0){
		int add = -1;
		if ((x + y) % 4 == 0) add = 1;

		return make_pair(x - 1, y + add);
	} else {
		int add = -1;
		if ((x + y) % 4 == 2) add = 1;

		return make_pair(x + add, y - 1);
	}
}

int construct_roads(vector<int> x, vector<int> y) {
 //    if (x.size() == 1) {
	// build({}, {}, {}, {});
 //        return 1;
 //    }
 //    std::vector<int> u, v, a, b;
 //    u.push_back(0);
 //    v.push_back(1);
 //    a.push_back(x[0]+1);
 //    b.push_back(y[0]-1);
 //    build(u, v, a, b);
 //    return 1;

	int n = x.size();
	vector <park> a(n);
	for (int i = 0; i < n; i++){
		a[i].i = i;
		a[i].x = x[i];
		a[i].y = y[i];
	}

	vector <int> u, v, u1, v1;

	sort(a.begin(), a.end(), [&](park x, park y){
		return x.x + x.y < y.x + y.y;
	});

	set <pair<int, int>> st;
	set <pair<int, int>> foun;
	map <pair<int, int>, int> mp;
	for (auto x : a){
		foun.insert({x.x, x.y});
		mp[{x.x, x.y}] = x.i;

		if (foun.find({x.x - 2, x.y}) != foun.end() && st.find(f(x.x, x.y, 0)) == st.end()){
			auto pi = f(x.x, x.y, 0);
			st.insert(pi);
			u.push_back(x.i);
			v.push_back(mp[make_pair(x.x - 2, x.y)]);
			u1.push_back(pi.first);
			v1.push_back(pi.second);
		}

		if (foun.find({x.x, x.y - 2}) != foun.end() && st.find(f(x.x, x.y, 1)) == st.end()){
			auto pi = f(x.x, x.y, 1);
			st.insert(pi);
			u.push_back(x.i);
			v.push_back(mp[make_pair(x.x, x.y - 2)]);
			u1.push_back(pi.first);
			v1.push_back(pi.second);
		}
	}

	for (int i = 0; i < n; i++) root[i] = i;

	for (int i = 0; i < (int)u.size(); i++){
		unite(u[i], v[i]);
	}

	for (int i = 0; i < n; i++){
		if (find(i) != find(0)) return 0;
	}

	build(u, v, u1, v1);
	return 1;
}

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