Submission #569209

#	Time	Username	Problem	Language	Result	Execution time	Memory
569209		pavement	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	307 ms	21356 KiB

railroad

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

using ll = long long;

#define pb push_back

ll ans;
int n, vsz, diff[400005], link[400005], sz[400005];
vector<int> vec;
vector<tuple<int, int, int> > ed;

int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[b] > sz[a]) swap(a, b);
	sz[a] += sz[b];
	link[b] = a;
}

int disc(int x) {
	return lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
	s.pb(1e9);
	t.pb(1);
	n = s.size();
	for (int i = 0; i < n; i++)
		vec.pb(s[i]), vec.pb(t[i]);
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	for (int i = 0; i < n; i++) {
		diff[disc(s[i])]++;
		diff[disc(t[i])]--;
	}
	vsz = vec.size();
	for (int i = 0; i < vsz; i++) {
		link[i] = i;
		sz[i] = 1;
	}
	for (int i = 0; i < n; i++)
		unite(disc(s[i]), disc(t[i]));
	for (int i = 0, bal = 0; i < vsz; i++) {
		bal += diff[i];
		if (i == vsz - 1) assert(bal == 0);
		if (bal > 0) ans += (ll)bal * (ll)(vec[i + 1] - vec[i]);
		if (bal) unite(i, i + 1);
	}
	for (int i = 0; i < vsz - 1; i++) ed.emplace_back(vec[i + 1] - vec[i], i, i + 1);
	sort(ed.begin(), ed.end());
	for (auto [w, u, v] : ed)
		if (find(u) != find(v)) unite(u, v), ans += (ll)w;
	return ans;
}

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