Submission #588893

#	Time	Username	Problem	Language	Result	Execution time	Memory
588893		mahra_IOI	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	480 ms	43256 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
map<int,int> m;
const int maxn = 4e5 + 10;
vector<int> grafo[maxn];
 
struct DSU{
	int pai[maxn];
	void init(int n){ for(int i=0; i<maxn; i++) pai[i] = i; }
	int find(int x){ return pai[x] == x ? x : pai[x] = find(pai[x]); }
	bool join(int a, int b){
		a = find(a), b = find(b);
		if(a == b) return 0;
		pai[b] = a; return 1;
	}
}dsu;
 
long long plan_roller_coaster(vector<int> s, vector<int> t) {
	int n = (int)s.size() + 1;
	s.push_back(1e9);
	t.push_back(1);
	vector<int> v;
	for(int x : s) v.push_back(x);
	for(int x : t) v.push_back(x);
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	int tt = 0;
	for(int x : v) m[x] = tt++;
	vector<int> sum(tt+1, 0);
	dsu.init(tt);
	for(int i=0; i<n; i++){
		int u = m[s[i]], v = m[t[i]];
		if(u == v) continue;
		dsu.join(u, v);
		++sum[u], --sum[v];
	}
	ll ans = 0;
	for(int i=0; i<tt; i++){
		if(i) sum[i] += sum[i-1];
		if(sum[i] != 0){
			dsu.join(i, i+1);
			ans += 1LL * max(sum[i], 0) * (v[i+1] - v[i]);
		}
	}
	vector<pii> q;
	for(int i=0; i+1<tt; i++) if(dsu.find(i) != dsu.find(i+1)) q.push_back({v[i+1] - v[i], i});
	sort(q.begin(), q.end());
	for(auto [w, i] : q) if(dsu.join(i, i+1)) ans += w;
	return ans;
}

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