Submission #1043640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043640		42kangaroo	Fountain Parks (IOI21_parks)	C++17	70 / 100	3593 ms	97220 KiB

parks

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

using namespace std;

struct Po {
	int x, y, f;
};

bool operator<(const Po& l, const Po& r) {
	return tie(l.x, l.y) < tie(r.x, r.y);
}

bool operator==(const Po& l, const Po& r) {
	return tie(l.x, l.y) == tie(r.x, r.y);
}

struct Ed {
	int s, t;
	Po be;
};

int find(int x, vector<int>& p) {
	if (p[x] == x) return x;
	return p[x] = find(p[x], p);
}

void unite(int a, int b, vector<int>& p) {
	a = find(a, p);
	b = find(b, p);
	p[a] = b;
}

using g_t = map<Po, set<Po>>;

int construct_roads(std::vector<int> x, std::vector<int> y) {
	vector<int> p(x.size());
	set<Po> par;
	for (int i = 0; i < x.size(); ++i) {
		p[i] = i;
		par.insert({x[i], y[i], i});
	}
	vector<Ed> eds;
	for (int i = 0; i < x.size(); ++i) {
		if (x[i] != 4 && par.find({x[i], y[i] + 2}) != par.end() && find(par.find({x[i], y[i] + 2})->f, p) != find(i, p)) {
			eds.push_back({par.find({x[i], y[i] + 2})->f, i});
			unite(par.find({x[i], y[i] + 2})->f, i, p);
		}
	}
	for (int i = 0; i < x.size(); ++i) {
		if (par.find({x[i] + 2, y[i]}) != par.end() && find(par.find({x[i] + 2, y[i]})->f, p) != find(i, p)) {
			eds.push_back({par.find({x[i] + 2, y[i]})->f, i});
			unite(par.find({x[i] + 2, y[i]})->f, i, p);
		}
	}
	for (int i = 0; i < x.size(); ++i) {
		if (par.find({x[i], y[i] + 2}) != par.end() && find(par.find({x[i], y[i] + 2})->f, p) != find(i, p)) {
			eds.push_back({par.find({x[i], y[i] + 2})->f, i});
			unite(par.find({x[i], y[i] + 2})->f, i, p);
		}
	}
	
	if (eds.size() + 1 < x.size()) return 0;
	g_t g;
	for (int j = 0; j < eds.size(); ++j) {
		if (x[eds[j].s] == x[eds[j].t]) {
			g[{x[eds[j].s] + 1, (y[eds[j].s] + y[eds[j].t])/2}].insert({x[eds[j].s] - 1,(y[eds[j].s] + y[eds[j].t])/2, j});
			g[{x[eds[j].s] - 1, (y[eds[j].s] + y[eds[j].t])/2}].insert({x[eds[j].s] + 1,(y[eds[j].s] + y[eds[j].t])/2, j});
		} else {
			g[{(x[eds[j].s] + x[eds[j].t] )/ 2, y[eds[j].s] + 1}].insert({(x[eds[j].s] + x[eds[j].t] )/ 2, y[eds[j].s] - 1, j});
			g[{(x[eds[j].s] + x[eds[j].t] )/ 2, y[eds[j].s] - 1}].insert({(x[eds[j].s] + x[eds[j].t] )/ 2, y[eds[j].s] + 1, j});
		}
	}
	queue<Po> ne;
	for (auto [st, en]: g) {
		if (en.size() == 1) ne.push(st);
	}
	while (!ne.empty()) {
		auto to = ne.front();
		ne.pop();
		if (g[to].empty()) {
			g.erase(to);
			continue;
		}
		eds[g[to].begin()->f].be = to;
		g[{g[to].begin()->x, g[to].begin()->y}].erase({to.x, to.y, g[to].begin()->f});
		if (g[{g[to].begin()->x, g[to].begin()->y}].size() == 1) ne.push({g[to].begin()->x, g[to].begin()->y});
		g.erase(to);
	}
	while (!g.empty()) {
		if (g.begin()->second.empty()) g.erase(g.begin());
		else {
			assert(g.begin()->second.size() == 2);
			auto to = g.begin()->first;
			eds[g[to].begin()->f].be = to;
			g[{g[to].begin()->x, g[to].begin()->y}].erase({to.x, to.y, g[to].begin()->f});
			if (g[{g[to].begin()->x, g[to].begin()->y}].size() == 1) ne.push({g[to].begin()->x, g[to].begin()->y});
			while (!ne.empty()) {
				to = ne.front();
				ne.pop();
				if (g[to].empty()) {
					g.erase(to);
					continue;
				}
				eds[g[to].begin()->f].be = to;
				g[{g[to].begin()->x, g[to].begin()->y}].erase({to.x, to.y, g[to].begin()->f});
				if (g[{g[to].begin()->x, g[to].begin()->y}].size() == 1) ne.push({g[to].begin()->x, g[to].begin()->y});
				g.erase(to);
			}
		}
	}
	vector<int> u(eds.size()), v(eds.size()), a(eds.size()), b(eds.size());
	for (int i = 0; i < eds.size(); ++i) {
		tie(u[i], v[i], a[i], b[i]) = tie(eds[i].s, eds[i].t, eds[i].be.x, eds[i].be.y);
	}
	build(u, v, a, b);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 0; i < x.size(); ++i) {
      |                  ~~^~~~~~~~~~
parks.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for (int i = 0; i < x.size(); ++i) {
      |                  ~~^~~~~~~~~~
parks.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i = 0; i < x.size(); ++i) {
      |                  ~~^~~~~~~~~~
parks.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int i = 0; i < x.size(); ++i) {
      |                  ~~^~~~~~~~~~
parks.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Ed>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for (int j = 0; j < eds.size(); ++j) {
      |                  ~~^~~~~~~~~~~~
parks.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Ed>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for (int i = 0; i < eds.size(); ++i) {
      |                  ~~^~~~~~~~~~~~

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