Submission #1185952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185952		pedroslrey	Roller Coaster Railroad (IOI16_railroad)	C++20	100 / 100	1741 ms	61564 KiB

railroad

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

using namespace std;
using lli = long long;

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

	map<int, int> deltas;
	++deltas[1]; --deltas[1e9];
	for (int i = 0; i < n; ++i) {
		++deltas[ys[i]]; --deltas[xs[i]];
	}

	map<int, int> rep;
	for (auto [u, _]: deltas)
		rep[u] = u;

	function<int (int)> find = [&](int u) { return rep[u] == u ? u : rep[u] = find(rep[u]); };
	function<void (int, int)> une = [&](int u, int v) { rep[find(u)] = find(v); };
	for (int i = 0; i < n; ++i)
		une(xs[i], ys[i]);

	int sum = 0; lli ans = 0;
	vector<tuple<int, int, int>> edges;
	for (auto it = deltas.begin(); next(it) != deltas.end(); ++it) {
		sum += it->second;
		
		if (sum < 0) ans += -1LL*sum*(next(it)->first - it->first);

		if (sum == 0) edges.emplace_back(next(it)->first - it->first, it->first, next(it)->first);
		else edges.emplace_back(0, it->first, next(it)->first);
	}

	sort(edges.begin(), edges.end());
	for (auto [c, u, v]: edges) if (find(u) != find(v)) {
		une(u, v); ans += c;
	}

	return ans;
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36