Submission #121188

#	Time	Username	Problem	Language	Result	Execution time	Memory
121188		WhipppedCream	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	460 ms	44480 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

int n;

const int maxN = 4e5+5;

int sw[maxN];
vector<int> adj[maxN];
int s[maxN], t[maxN];

struct dsu
{
	int par[maxN];
	int cc;
	dsu(int n = 0)
	{
		for(int i = 0; i< n; i++) par[i] = i;
		cc = n;
	}
	int findset(int x)
	{
		if(x == par[x]) return x;
		return par[x] = findset(par[x]);
	}
	void unionset(int x, int y)
	{
		int a = findset(x), b = findset(y);
		if(a == b) return;
		cc--;
		par[a] = b;
	}
};

dsu foo;

ll plan_roller_coaster(vector<int> S, vector<int> T)
{
	n = S.size();
	for(int i = 0; i< n; i++)
	{
		s[i] = S[i];
		t[i] = T[i];
	}
	vector<int> all;
	for(int i = 0; i< n; i++)
	{
		all.pb(s[i]); all.pb(t[i]);
	}
	all.pb(1); all.pb(1e9);
	sort(all.begin(), all.end());
	all.resize(unique(all.begin(), all.end())-all.begin());

	foo = dsu( (int) all.size());
	sw[0]++;
	sw[all.size()-1]--;
	adj[all.size()-1].pb(0);
	foo.unionset(all.size()-1, 0);
	for(int i = 0; i< n; i++)
	{
		int ss = lower_bound(all.begin(), all.end(), s[i])-all.begin();
		int tt = lower_bound(all.begin(), all.end(), t[i])-all.begin();
		sw[ss]--;
		sw[tt]++;
		adj[ss].pb(tt);
		foo.unionset(ss, tt);
	}
	int run = 0;
	ll base = 0;
	for(int i = 0; i+1< (int) all.size(); i++)
	{
		run += sw[i];
		if(run> 0) 
		{
			adj[i].pb(i+1);
			foo.unionset(i, i+1);
		}
		if(run< 0)
		{
			adj[i+1].pb(i);
			base += 1LL*-run*(all[i+1]-all[i]);
			foo.unionset(i+1, i);
		}
	}
	vector< ii > edges;
	for(int i = 0; i+1< (int) all.size(); i++)
	{
		edges.pb({all[i+1]-all[i], i});
	}
	sort(edges.begin(), edges.end());
	for(ii kk : edges)
	{
		int w = kk.X, u = kk.Y;
		int x = foo.findset(u), y = foo.findset(u+1);
		if(x == y) continue;
		foo.unionset(x, y);
		base += w;
		if(foo.cc == 1) break;
	}
	return base;
}

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