제출 #997037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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;
}

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