Submission #669261

#	Time	Username	Problem	Language	Result	Execution time	Memory
669261		flappybird	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	230 ms	18756 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

#define MAX 404040
#define INF 1000000001

vector<int> all;
int deg[MAX];

int N;

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

void uni(int x, int y) {
	x = find(x);
	y = find(y);
	p[x] = y;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	N = s.size();
	for (auto v : s) all.push_back(v);
	for (auto v : t) all.push_back(v);
	all.push_back(INF);
	all.push_back(0);
	sort(all.begin(), all.end());
	all.erase(unique(all.begin(), all.end()), all.end());
	int X = all.size();
	int i;
	for (i = 0; i < X; i++) p[i] = i;
	for (auto& v : s) v = lower_bound(all.begin(), all.end(), v) - all.begin();
	for (auto& v : t) v = lower_bound(all.begin(), all.end(), v) - all.begin();
	for (i = 0; i < N; i++) {
		deg[s[i]]--;
		deg[t[i]]++;
		uni(s[i], t[i]);
	}
	deg[0]++;
	deg[X - 1]--;
	ll ans = 0;
	for (i = 1; i < X; i++) {
		if (deg[i - 1]) {
			uni(i - 1, i);
			if (deg[i - 1] < 0) ans += 1ll * -(ll)deg[i - 1] * ((ll)all[i] - all[i - 1]);
			deg[i] += deg[i - 1];
		}
	}
	vector<pii> vpi;
	for (i = 1; i < X; i++) vpi.emplace_back(all[i] - all[i - 1], i);
	sort(vpi.begin(), vpi.end());
	for (auto& [c, v] : vpi) {
		if (find(v - 1) != find(v)) {
			uni(v - 1, v);
			ans += c;
		}
	}
	return ans;
}

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