Submission #1050578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050578		Alihan_8	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	169 ms	27700 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define all(x) x.begin(), x.end()
#define ln '\n'
#define ar array

using i64 = long long;

struct Dsu{
	vector <int> fa;
	
	Dsu(int n){
		fa.resize(n);
		iota(all(fa), 0);
	}
	
	int get(int x){
		return x ^ fa[x] ? fa[x] = get(fa[x]) : x;
	}
	
	bool merge(int u, int v){
		u = get(u), v = get(v);
		
		if ( u == v ) return false;
		
		fa[v] = u;
		
		return true;
	}
};

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	int n = s.size(), m;
	
	vector <int> p;
	
	s.pb(2e9), t.pb(1);
	
	{ // compression
		for ( int i = 0; i <= n; i++ ){
			p.pb(s[i]); p.pb(t[i]);
		}
		
		sort(all(p));
		p.resize(unique(all(p)) - p.begin());
		
		m = p.size();
		
		for ( int i = 0; i <= n; i++ ){
			s[i] = lower_bound(all(p), s[i]) - p.begin();
			t[i] = lower_bound(all(p), t[i]) - p.begin();
		}
 	}
 	
 	vector <int> pf(m);
 	
 	for ( int i = 0; i <= n; i++ ){
		pf[t[i]]--;
		pf[s[i]]++;
	}
	
	for ( int i = 1; i < m; i++ ){
		pf[i] += pf[i - 1];
	}
		
	Dsu ds(m);
	
	for ( int i = 0; i <= n; i++ ){
		ds.merge(s[i], t[i]);
		
		//~ cout << s[i] << " " << t[i] << ln;
	}
	
	i64 ans = 0;
	
	vector <ar<i64,3>> e;
	
	for ( int i = 0; i + 1 < m; i++ ){
		if ( pf[i] > 0 ){
			ans += pf[i] * 1LL * (p[i + 1] - p[i]);
			
			ds.merge(i, i + 1);
		}
		
		if ( pf[i] < 0 ) ds.merge(i, i + 1);
		
		e.pb({p[i + 1] - p[i], i, i + 1});
	}
	
	//~ cout << ans << ln;
	
	sort(all(e));
	
	for ( auto &[w, u, v]: e ){
		ans += ds.merge(u, v) * w;
	}
	
	return ans;
}

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