Submission #925414

#	Time	Username	Problem	Language	Result	Execution time	Memory
925414		Itamar	Fountain Parks (IOI21_parks)	C++17	45 / 100	1141 ms	118988 KiB

parks

using namespace std;
#include <vector>
#include "parks.h"
#include <map>
#define pi pair<int,int>
#define vi vector<int>
const int siz = 2e5 + 2;
map<pi, int> m;
int my[siz];
vi col[siz];
#include <set>
bool con(int a, int b) {
	if (my[a] == my[b])return 0;
	a = my[a], b = my[b];
	if (col[a].size() > col[b].size())swap(a, b);
	for (int x : col[a]) {
		my[x] = b;
		col[b].push_back(x);
	}
	return 1;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
	int n = x.size();
	for (int i = 0; i < n; i++) {
		m[{x[i], y[i]}] = i + 1;
	}
	vector<pi> ed1, ed2;
	for (int i = 0; i < n; i++) {
		if (m[{x[i] + 2, y[i]}])ed1.push_back({ i+1,m[{x[i] + 2, y[i]}] });
		if (m[{x[i], y[i] + 2}])ed2.push_back({ i+1,m[{x[i],y[i] + 2}] });
	}
	vector<pi> ed; for (pi p : ed2)ed.push_back(p); for (pi p : ed1)ed.push_back(p);
	vector<pi> ans;
	for (int i = 0; i <= n; i++) {
		my[i] = i; col[i].push_back(i);
	}
	for (pi e : ed) {
		if (con(e.first, e.second))ans.push_back(e);
	}
	if (ans.size()+1 < n )return 0;
	vi ans1(n - 1), ans2(n - 1), ans3(n - 1), ans4(n - 1);

	for (int i = 0; i < n - 1; i++) {
		ans1[i] = ans[i].first - 1; ans2[i] = ans[i].second - 1;
	}
	map<pi, vi> fr;
	vector<vector<pi>> fr2(n - 1);
	for (int i = 0; i < n - 1; i++) {
		if (x[ans[i].first - 1] == x[ans[i].second - 1]) {
			int mid = (y[ans[i].first - 1] + y[ans[i].second - 1]) / 2;
			fr[{x[ans[i].first - 1]-1, mid}].push_back(i);
			fr[{x[ans[i].first - 1]+1, mid}].push_back(i);
			fr2[i].push_back({ x[ans[i].first - 1]-1, mid });
			fr2[i].push_back({ x[ans[i].first - 1]+1, mid });
		}
		else {
			int mid = (x[ans[i].first - 1] + x[ans[i].second - 1]) / 2;
			fr[{mid,y[ans[i].first - 1]+1}].push_back(i);
			fr[{mid,y[ans[i].first - 1]-1}].push_back(i);
			fr2[i].push_back( {mid,y[ans[i].first - 1]-1 });
			fr2[i].push_back( {mid,y[ans[i].first - 1]+1} );
		}
	}
	vector<pi> deg1;
	for (pair<pi, vi> p : fr)if (p.second.size() == 1)deg1.push_back(p.first);

	while(!deg1.empty()){

		pi poi = deg1.back();
		deg1.pop_back();
			while (fr[poi].size() == 1) {
				int i = fr[poi][0];
				fr[poi].pop_back();
				if (fr2[i].back() != poi)swap(fr2[i][0], fr2[i][1]);
				fr2[i].pop_back();
				ans3[i] = poi.first, ans4[i] = poi.second;
				if (fr2[i].size() == 1) {
					poi = fr2[i][0];
					if (fr[poi].size()) {
						if (fr[poi].back() != i)swap(fr[poi][0], fr[poi][1]);
						fr[poi].pop_back();
						if (fr[poi].size() == 1)deg1.push_back(poi);
					}
				}
			}
	}
	for (pair<pi, vi> p : fr) {
		pi poi = p.first;
		if (p.second.size() == 2)fr[poi].pop_back();
		while (fr[poi].size() == 1) {
			int i = fr[poi][0];
			fr[poi].pop_back();
			if (fr2[i].back() != poi)swap(fr2[i][0], fr2[i][1]);
			fr2[i].pop_back();
			ans3[i] = poi.first, ans4[i] = poi.second;
			if (fr2[i].size() == 1) {
				poi = fr2[i][0];
				if (fr[poi].size()) {
					if (fr[poi].back() != i)swap(fr[poi][0], fr[poi][1]);
					fr[poi].pop_back();
				}
			}
		}
	}
	build(ans1, ans2, ans3, ans4);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:42:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |  if (ans.size()+1 < n )return 0;
      |      ~~~~~~~~~~~~~^~~

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