제출 #997042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997042		0npata	분수 공원 (IOI21_parks)	C++17	70 / 100	789 ms	153144 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(auto red_point : red_point_edges) {
		if(red_point.snd.size() == 1) {
			int edge = *(red_point.snd.begin());
			ass[edge] = true;
			ass_xs[edge] = red_point.fst.fst;
			ass_ys[edge] = red_point.fst.snd;
		}
	}

	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;
}

컴파일 시 표준 에러 (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