Submission #721232

#	Time	Username	Problem	Language	Result	Execution time	Memory
721232		n1k	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	320 ms	20276 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"

#define ll long long
#define vt vector
#define pb push_back
#define ar array
#define all(x) (x).begin(), (x).end()
#define sz(x) (x).size()

using namespace std;

/*
 1. simplify
 2. add new elements
 3. brute force solution
 4. optimize
 5. start implementing
*/

// --- templates ---
// --- code ---

vt<int> p;

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

bool join(int u, int v){
	if((u = find(u)) == (v = find(v))){
		return false;
	}
	p[u] = v;
	return true;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	int n = sz(s);
	vt<int> comp = s;
	comp.insert(comp.end(), all(t));

	sort(all(comp));

	vt<int> a(sz(comp));
	p.resize(sz(comp));
	iota(all(p), 0);

	for(int i = 0; i < n; i++){
		s[i] = lower_bound(all(comp), s[i]) - comp.begin();
		t[i] = lower_bound(all(comp), t[i]) - comp.begin();

		a[s[i]]++;
		a[t[i]]--;

		join(s[i], t[i]);
	}
	ll ans = 0;
	vt<ar<int, 2>> e;
	for(int i = 0; i < sz(comp) - 1; i++){
		a[i + 1] += a[i];
		ans += max((ll)0, ((ll) (a[i] - 1)) * (comp[i + 1] - comp[i]));
		if(a[i] != 1){
			join(i, i + 1);
		}
		e.pb({comp[i + 1] - comp[i], i});
	}
	sort(all(e));
	for(int i = 0; i < sz(e); i++){
		if(join(e[i][1], e[i][1] + 1)){
			ans += e[i][0];
		}
	}
	return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(int i = 0; i < sz(comp) - 1; i++){
      |                 ~~^~~~~~~~~~~~~~
railroad.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i = 0; i < sz(e); i++){
      |                   ^

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