Submission #233090

#	Time	Username	Problem	Language	Result	Execution time	Memory
233090		islingr	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	124 ms	13580 KiB

railroad

#include <algorithm>
#include <vector>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)
#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)
#define sz(x) int((x).size())
#define eb(x...) emplace_back(x)
#define f first
#define s second

const int N = 1 << 18;
int nxt[N], rnk[N];

int head(int u) { return nxt[u] != -1 ? nxt[u] = head(nxt[u]) : u; }
bool unite(int u, int v) {
	u = head(u); v = head(v);
	if (u == v) return false;
	if (rnk[u] > rnk[v]) nxt[v] = u;
	else {
		nxt[u] = v;
		if (rnk[u] == rnk[v]) ++rnk[v];
	}
	return true;
}

const int inf = 2e9;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

ll plan_roller_coaster(vi s, vi t) {
	ll ans = 0;
	
	int n = sz(s) + 1; s.eb(inf); t.eb(1);

	vector<int> p = s;
	p.insert(end(p), all(t));
	sort(all(p)); p.erase(unique(all(p)), end(p));	
	int m = sz(p); rep(u, 0, m) nxt[u] = -1;

	vector<int> sum(m--);
	rep(i, 0, n) {
		int l = lb(all(p), s[i]) - begin(p), r = lb(all(p), t[i]) - begin(p);
		unite(l, r);
		++sum[l]; --sum[r];
	}
	rep(i, 0, m) sum[i + 1] += sum[i];

	vector<pii> e;
	rep(i, 0, m) {
		ll d = p[i + 1] - p[i];
		if (sum[i]) {
			unite(i + 1, i);
			if (sum[i] > 0) ans += sum[i] * d;
		} else e.eb(d, i);
	}
	sort(all(e));
	trav(x, e) if (unite(x.s, x.s + 1)) ans += x.f;
	return ans;
}

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