제출 #292542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292542		amoo_safar	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	300 ms	24416 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>

#define pb push_back
#define all(x) x.begin(), x.end()
#define int ll

using namespace std;

typedef long long ll;

const int N = 4e5 + 10;

int par[N];
int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
bool Unite(int u, int v){
	//cerr << "# " << u << ' ' << v << '\n';
	u = Find(u); v = Find(v);
	if(u == v) return false;
	par[u] = v;
	return true;
}
int deg[N];
ll plan_roller_coaster(vector<int32_t> s, vector<int32_t> t){
	int n = s.size();
	
	iota(par, par + N, 0);
	vector<int> V;
	for(auto x : s) V.pb(x);
	for(auto x : t) V.pb(x);
	
	V.pb(0);
	V.pb(1e9 + 1);
	sort(all(V));
	V.resize(unique(all(V)) - V.begin());
	int m = V.size();
	for(auto &x : s) x = lower_bound(all(V), x) - V.begin();
	for(auto &x : t) x = lower_bound(all(V), x) - V.begin();
	for(auto x : s) deg[x] ++;
	for(auto x : t) deg[x] --;
	
	for(int i = 0; i < n; i++) Unite(s[i], t[i]);
	//for(int i = 0; i < n; i++) cerr << s[i] << ' ' << t[i] << '\n';

	vector< pair<int, int> > E;
	deg[0] --;
	deg[m - 1]++;
	
	
	ll ans = 0;
	for(int i = 0; i + 1 < m; i++){
		int cnt = -deg[i];
		if(cnt == 0) continue;
		Unite(i, i + 1);
		//cerr << i << ' ' << i + 1 << '\n';
		deg[i + 1] += deg[i];
		if(cnt < 0)
			ans += abs(cnt) * (V[i + 1] - V[i]);
	}
	for(int i = 0; i + 1 < m; i++){
		E.pb({V[i + 1] - V[i], i});
	}
	assert(deg[m - 1] == 0);
	sort(all(E));
	for(auto [w, i] : E){
		if(Unite(i, i + 1)){
			ans += w;
			//cerr << "$$ " << w << '\n';
		}
	}
	return ans;
}

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