Submission #997037

#	Time	Username	Problem	Language	Result	Execution time	Memory
997037		0npata	Fountain Parks (IOI21_parks)	C++17	70 / 100	776 ms	154172 KiB

parks

#include "parks.h"

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

#define vec vector
#define coord pair<int, int>
#define fst first
#define snd second

void dfs(int u, set<int>& vis, vec<vec<int>>& g, vec<int>& us, vec<int>& vs) {
	for(int v : g[u]) {
		if(vis.find(v) != vis.end()) {
			continue;
		}
		vis.insert(v);
		us.push_back(u);
		vs.push_back(v);

		dfs(v, vis, g, us, vs);
	}
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
	int n = x.size();

	// construct graph
	map<coord, int> points;
	for(int i = 0; i<n; i++) points.insert({{x[i], y[i]}, i});

	vec<vec<int>> g(n);

	for(int i = 0; i<n; i++) {
		vec<coord> pot_neigh = {{x[i]+2, y[i]}, {x[i], y[i]+2}};
		for(coord c : pot_neigh) {
			auto it = points.find(c);
			if(it == points.end()) continue;
			int j = (*it).snd;
			g[i].push_back(j);
			g[j].push_back(i);
		}
	}

	// use dfs tree of the graph to construct u and v
	vec<int> us(0), vs(0);
	set<int> vis;
	vis.insert(0);
	dfs(0, vis, g, us, vs);

	if(us.size() != n-1) {
		return 0;
	}

	// for each edge of the tree, create set of two red points it can use, and for each red point, corresponding edges that want it
	vec<set<coord>> edge_red_points(n-1);
	map<coord, set<int>> red_point_edges;

	for(int i = 0; i<n-1; i++) {
		vec<coord> eps{{x[us[i]], y[us[i]]}, {x[vs[i]], y[vs[i]]}};
		sort(eps.begin(), eps.end());

		set<coord> red_points;

		if(eps[0].fst == eps[1].fst) {
			red_points.insert({eps[0].fst+1, (eps[0].snd+eps[1].snd)/2});
			red_points.insert({eps[0].fst-1, (eps[0].snd+eps[1].snd)/2});
		}
		else {
			red_points.insert({(eps[0].fst+eps[1].fst)/2, eps[0].snd+1});
			red_points.insert({(eps[0].fst+eps[1].fst)/2, eps[0].snd-1});
		}

		edge_red_points[i] = red_points;

		for(coord _coord : red_points) {
			red_point_edges[_coord].insert(i);
		}
	}

	// assign red points to edges, iterate from first edge to last, if it isn't assigned, give it any of the two, as long as there are edges that have only one avilable as consequence assign them that one availble
	vec<bool> ass(n-1, false);

	vec<int> ass_xs(n-1);
	vec<int> ass_ys(n-1);

	for(int i = 0; i<n-1; i++) {
		if(ass[i]) continue;

		assert(edge_red_points[i].size() == 2);
		coord red_point = *edge_red_points[i].begin();

		red_point_edges[red_point].erase(i);
		edge_red_points[i].erase(red_point);

		ass[i] = true;
		ass_xs[i] = red_point.fst;
		ass_ys[i] = red_point.snd;


		vec<coord> rem_red_points{red_point};

		while(rem_red_points.size() > 0) {
			red_point = rem_red_points.back();
			rem_red_points.pop_back();

			for(int j : red_point_edges[red_point]) {
				if(ass[j]) {
					continue;
				}
				edge_red_points[j].erase(red_point);
				assert(edge_red_points[j].size() == 1);
				coord other = *edge_red_points[j].begin();
				ass[j] = true;
				ass_xs[j] = other.fst;
				ass_ys[j] = other.snd;

				red_point_edges[other].erase(j);
				edge_red_points[j].erase(red_point);

				rem_red_points.push_back(other);
			}
		}
	}

	build(us, vs, ass_xs, ass_ys);

	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:50:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |  if(us.size() != n-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