Submission #188170

#	Time	Username	Problem	Language	Result	Execution time	Memory
188170		oolimry	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	330 ms	20916 KiB

railroad

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

long long balance[400005]; int p[400005];
vector<pair<int, pair<int,int> > > edges;

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

bool unionSet(int u, int v){
	int x = findSet(u);
	int y = findSet(v);
	if(x == y) return false;
	p[x] = y;
	return true;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	s.push_back(2e9); t.push_back(1);
    int n = (int) s.size();
	
    vector<long long> points;
    for(int i = 0;i < n;i++) points.push_back(s[i]), points.push_back(t[i]);
    
    sort(points.begin(),points.end());
    points.erase(unique(points.begin(),points.end()), points.end());
    for(int i = 0;i < (int) points.size();i++) p[i] = i;
    
    for(int i = 0;i < n;i++){
		s[i] = lower_bound(points.begin(),points.end(),s[i]) - points.begin();
		t[i] = lower_bound(points.begin(),points.end(),t[i]) - points.begin();
		balance[s[i]]++;
		balance[t[i]]--;
		unionSet(s[i],t[i]);
	}
	
	long long ans = 0, acc = 0;
	for(int i = 0;i < (int) points.size() - 1;i++){
		acc += balance[i];
		if(acc == 0) edges.push_back({points[i+1] - points[i], {i, i+1}});
		else{
			unionSet(i,i+1);
			if(acc > 0) ans += (points[i+1] - points[i]) * acc;
		}
	}
	sort(edges.begin(),edges.end());
	for(auto& e : edges){
		if(unionSet(e.second.first,e.second.second)){
			ans += e.first;
		}
	}
    return ans;
}

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