Submission #986972

#	Time	Username	Problem	Language	Result	Execution time	Memory
986972		pedroslrey	Fountain Parks (IOI21_parks)	C++17	45 / 100	785 ms	78264 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"

using namespace std;

int construct_roads(vector<int> xs, vector<int> ys) {
	int n = xs.size();

	map<pair<int, int>, int> points;
	for (int i = 0; i < n; ++i)
		points[make_pair(xs[i], ys[i])] = i;

	vector<int> rep(n); int comps = n;
	for (int i = 0; i < n; ++i)
		rep[i] = i;

	function<int (int)> find = [&rep, &find](int u) {
		if (rep[u] == u) return u;
		return rep[u] = find(rep[u]);
	};

	function<void (int, int)> une = [&rep, &comps, &find](int u, int v) {
		u = find(u); v = find(v);

		if (u == v) return;
		rep[u] = v;

		--comps;
	};

	vector<int> us, vs;
	for (int i = 0; i < n; ++i) {
		pair<int, int> lft{xs[i], ys[i] + 2}, up{xs[i] + 2, ys[i]};
		if (points.find(lft) != points.end()) {
			us.push_back(i);
			vs.push_back(points[lft]);
			une(us.back(), vs.back());
		}
		if (points.find(up) != points.end()) {
			us.push_back(i);
			vs.push_back(points[up]);
			une(us.back(), vs.back());
		}
	}

	if (comps > 1) return 0;

	map<pair<int, int>, int> mp;
	vector<pair<int, int>> benches;
	vector<vector<pair<int, int>>> graph;

	function<int (int, int)> vertex = [&mp, &graph, &benches](int x, int y) {
		pair<int, int> p{x, y};
		if (mp.find(p) == mp.end()) {
			benches.push_back(p);
			mp[p] = graph.size();
			graph.emplace_back();
		}

		return mp[p];
	};

	function<void (int, int, int)> add_edge = [&graph](int u, int v, int idx) {
		graph[u].emplace_back(v, idx);
		graph[v].emplace_back(u, idx);

		// cerr << "EDGE " << u << " " << v << " " << idx << "\n";
	};

	for (int i = 0; i < us.size(); ++i) {
		int x1 = xs[us[i]], y1 = ys[us[i]];
		int x2 = xs[vs[i]], y2 = ys[vs[i]];

		if (x1 == x2) {
			if (y1 > y2) swap(y1, y2);
			add_edge(vertex(x1 + 1, y1 + 1), vertex(x1 - 1, y1 + 1), i);
		}
		else {
			if (x1 > x2) swap(x1, x2);
			add_edge(vertex(x1 + 1, y1 + 1), vertex(x1 + 1, y1 - 1), i);
		}
	}

	for (auto &xs: graph) assert(xs.size() <= 2);

	vector<bool> marc(benches.size());
	vector<int> as(us.size()), bs(us.size());
	for (int i = 0; i < benches.size(); ++i) if (graph[i].size() == 1) {
		int u = i;
		while (!marc[u]) {
			marc[u] = true;
			for (auto [v, idx]: graph[u]) if (as[idx] == 0){
				as[idx] = benches[u].first;
				bs[idx] = benches[u].second;
				u = v;
				break;
			}
		}
	}

	for (int i = 0; i < benches.size(); ++i) {
		int u = i;
		while (!marc[u]) {
			marc[u] = true;
			for (auto [v, idx]: graph[u]) if (as[idx] == 0){
				as[idx] = benches[u].first;
				bs[idx] = benches[u].second;
				u = v;
				break;
			}
		}
	}

	build(us, vs, as, bs);

	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for (int i = 0; i < us.size(); ++i) {
      |                  ~~^~~~~~~~~~~
parks.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for (int i = 0; i < benches.size(); ++i) if (graph[i].size() == 1) {
      |                  ~~^~~~~~~~~~~~~~~~
parks.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for (int i = 0; i < benches.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~~

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