Submission #388646

#	Time	Username	Problem	Language	Result	Execution time	Memory
388646		alireza_kaviani	Roller Coaster Railroad (IOI16_railroad)	C++11	100 / 100	305 ms	24312 KiB

railroad

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

typedef long long ll;
typedef pair<int, int> pii;

#define all(x)		(x).begin() , (x).end()
#define SZ(x)		int(x.size())
#define sep			' '
#define X			first
#define Y			second

const int MAXN = 5e5 + 10;

ll ps[MAXN] , par[MAXN] , sz[MAXN];
vector<ll> compress;

int Find(int v){
	return (par[v] == -1 ? v : par[v] = Find(par[v]));
}

void Union(int v , int u){
//	cout << "U " << v << sep << u << endl;
	v = Find(v); u = Find(u);
	if(v == u)	return;
	if(sz[v] < sz[u])	swap(v , u);
	par[v] = u;
	sz[v] += sz[u];
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
	fill(par , par + MAXN , -1);
	fill(sz , sz + MAXN , 1);
	int n = (int) s.size();
	for(int i = 0 ; i < n ; i++){
		compress.push_back(s[i]);
		compress.push_back(t[i]);
	}
	sort(all(compress));
	compress.resize(unique(all(compress)) - compress.begin());
	for(int i = 0 ; i < n ; i++){
//		cout << s[i] << sep << t[i] << endl;
		s[i] = lower_bound(all(compress) , s[i]) - compress.begin();
		t[i] = lower_bound(all(compress) , t[i]) - compress.begin();
		ps[s[i]]++; ps[t[i]]--; Union(s[i] , t[i]);
//		cout << s[i] << sep << t[i] << endl;
	}
	ll ans = 0;
	vector<pii> vec;
	for(int i = 0 ; i + 1 < SZ(compress) ; i++){
		ps[i + 1] += ps[i];
		ans += max(0ll , ps[i] - 1) * (compress[i + 1] - compress[i]);
		if(ps[i] != 1)	Union(i , i + 1);
		else{
			vec.push_back({compress[i + 1] - compress[i] , i});
		}
	}
	sort(all(vec));
	for(pii i : vec){
//		cout << "E " << i.X << sep << i.Y << endl;
		if(Find(i.Y) != Find(i.Y + 1)){
			Union(i.Y , i.Y + 1);
			ans += i.X;
		}
	}
	return ans;
}

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