Submission #140796

#	Time	Username	Problem	Language	Result	Execution time	Memory
140796		Namnamseo	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	699 ms	36400 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

#define eb emplace_back
#define x first
#define y second

using pp=pair<int,int>;
using ll=long long;

map<int,int> df;

const int inf = int(1e9) + 10;
const int maxn = int(4e5) + 10;

int par[maxn];
vector<pp> D;

int R(int x){ return (par[x]==x) ? x : (par[x]=R(par[x])); }

vector<tuple<int,int,int>> ev;

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

	for(int i=0; i<n; ++i) {
		df[s[i]] += -1;
		df[t[i]] += +1;
	}

	df[0] += +1;
	df[inf] += -1;

	D = vector<pp>(df.begin(), df.end());

	int sz = D.size();
	iota(par, par+sz, 0);

	ll ans = 0;
	int lev = 0, last = 0;

	for(int i=0; i<sz; ++i) {
		auto &tmp = D[i];
		if(lev < 0) {
			ans += (tmp.x - last) * 1ll * (-lev);
		}
		if(lev && i) {
			par[R(i-1)] = i;
		}
		last = tmp.x;
		lev += tmp.y;
	}

	auto fnd = [&](int x){ return int(lower_bound(D.begin(), D.end(), pp(x, -inf)) - D.begin()); };
	for(int i=0; i<n; ++i) {
		par[R(fnd(s[i]))] = R(fnd(t[i]));
	}
	par[R(fnd(0))] = R(fnd(inf));

	for(int i=0; i+1<sz; ++i) {
		int va = R(i), vb = R(i+1);
		if(va != vb) ev.eb(D[i+1].x-D[i].x, va, vb);
	}

	sort(ev.begin(), ev.end());
	for(auto &tmp:ev) {
		int v, a, b; tie(v, a, b) = tmp;
		if(R(a) != R(b)) {
			ans += v;
			par[R(a)] = R(b);
		}
	}

	return ans;
}

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