Submission #163319

#	Time	Username	Problem	Language	Result	Execution time	Memory
163319		dolphingarlic	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	349 ms	13140 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
typedef long long ll;

int X[404040];
int balance[404040], din[404040], dout[404040];
vector<pair<int, pair<int, int>>> edges;

int component[404040];
int find(int a) {
	while (component[a] != a) component[a] = component[component[a]], a = component[a];
	return a;
}
void onion(int a, int b) {
	component[find(a)] = component[find(b)];
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
	int n = s.size();

	FOR(i, 0, n) {
		X[i * 2] = s[i];
		X[i * 2 + 1] = t[i];
	}
	X[2 * n] = 1;
	X[2 * n + 1] = 2e9;

	sort(X, X + 2 * n + 2);
	FOR(i, 0, 2 * n + 2) component[i] = i;

	FOR(i, 0, n) {
		s[i] = lower_bound(X, X + 2 * n + 2, s[i]) - X;
		t[i] = lower_bound(X, X + 2 * n + 2, t[i]) - X;
		
		din[t[i]]++;
		dout[s[i]]++;
		onion(t[i], s[i]);
	}
	din[0]++;
	dout[2 * n + 1]++;
	onion(0, 2 * n + 1);

	ll ans = 0;
	int sm = 0;
	FOR(i, 0, 2 * n + 1) {
		sm += dout[i] - din[i];
		if (sm < 0) onion(i, i + 1);
		else if (sm == 0) edges.push_back({X[i + 1] - X[i], {i, i + 1}});
		else ans += sm * (X[i + 1] - X[i]);
	}

	sort(edges.begin(), edges.end());
	for (auto& i : edges) {
		if (find(i.second.first) != find(i.second.second)) {
			onion(i.second.first, i.second.second);
			ans += i.first;
		}
	}

	return ans;
}

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