Submission #1026040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026040		0npata	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	752 ms	76372 KiB

railroad

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

using namespace std;

#define int long long
#define vec vector

const int INF = 1e9+1;

struct DSU {
	vec<int> par;
	vec<int> sz;

	DSU(int n) {
		par = vec<int>(n);
		sz = vec<int>(n, 1);
		iota(par.begin(), par.end(), 0);
	}

	int root(int u) {
		if(par[u] == u) return u;
		par[u] = root(par[u]);
		return par[u];
	}

	bool join(int u, int v) {
		u = root(u);
		v = root(v);
		if(u == v) return false;
		if(sz[v] > sz[u]) swap(u, v);
		par[v] = u;
		sz[u] += sz[v];
		return true;
	}
};

int plan_roller_coaster(vec<int32_t> s, vec<int32_t> t) {
    int32_t n = (int32_t) s.size();

	map<int, int> bal_dif;

	for(int i = 0; i<n; i++) {
		bal_dif[s[i]]++;
		bal_dif[t[i]]--;
	}

	bal_dif[1]--;
	bal_dif[INF]++;

	int bal = 0;

	int prev = 0;

	int ans = 0;

	set<pair<int, pair<int, int>>> edges;

	DSU dsu(bal_dif.size()+5);

	map<int, int> eps_ind;
	int cnt = 1;

	eps_ind[0] = 0;

	for(auto [i, b_add] : bal_dif) {
		eps_ind[i] = cnt;
		if(bal > 0) {
			ans += bal * (i-prev);
			dsu.join(eps_ind[i], eps_ind[prev]);
		}
		else if(bal < 0) {
			dsu.join(eps_ind[i], eps_ind[prev]);
		}
		else if (prev != 0) {
			edges.insert({i-prev, {eps_ind[prev], eps_ind[i]}});
		}
		bal += b_add;
		prev = i;

		cnt++;
	}

	dsu.join(eps_ind[1], eps_ind[INF]);
	for(int i = 0; i<n; i++) {
		dsu.join(eps_ind[s[i]], eps_ind[t[i]]);
	}

	//cerr << ans << '\n';

	while(edges.size() > 0) {
		auto it = edges.begin();
		auto [w, eps] = *it;
		edges.erase(it);

		if(dsu.join(eps.first, eps.second)) {
			ans += w;
		}
	}


    return ans;
}

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