Submission #722580

#	Time	Username	Problem	Language	Result	Execution time	Memory
722580		ymm	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	433 ms	51268 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 400010;

vector<int> A[N];
int vis[N];

void dfs(int v, int c)
{
	vis[v] = c;
	for (int u : A[v])
		if (vis[u] == -1)
			dfs(u, c);
}

namespace dsu {
	int par[N];
	int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
	bool unite(int v, int u) {
		v = rt(v);
		u = rt(u);
		if (v == u)
			return 0;
		par[u] = v;
		return 1;
	}
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
	s.push_back(1e9+10);
	t.push_back(1);
	int n = s.size();
	vector<int> cmp;
	Loop (i,0,n) {
		cmp.push_back(s[i]);
		cmp.push_back(t[i]);
	}
	sort(cmp.begin(), cmp.end());
	cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
	int m = cmp.size();
	vector<int> val(m);
	Loop (i,0,n) {
		int x = lower_bound(cmp.begin(), cmp.end(), s[i]) - cmp.begin();
		int y = lower_bound(cmp.begin(), cmp.end(), t[i]) - cmp.begin();
		A[x].push_back(y);
		A[y].push_back(x);
		val[x]--;
		val[y]++;
	}
	int cnt = 0;
	ll ans = 0;
	Loop (i,0,m-1) {
		cnt += val[i];
		if (cnt < 0)
			ans += (ll)(cmp[i+1] - cmp[i]) * -cnt;
		if (cnt) {
			A[i].push_back(i+1);
			A[i+1].push_back(i);
		}
	}
	int k = 0;
	memset(vis, -1, sizeof(vis));
	Loop (i,0,m) {
		if (vis[i] == -1)
			dfs(i, k++);
	}
	memset(dsu::par, -1, sizeof(dsu::par));
	vector<tuple<int,int,int>> E;
	Loop (i,0,m-1)
		E.push_back({cmp[i+1] - cmp[i], vis[i], vis[i+1]});
	sort(E.begin(), E.end());
	for (auto [w, v, u] : E) {
		if (dsu::unite(v, u)) {
			ans += w;
		}
	}
	return ans;
}

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