Submission #826296

#	Time	Username	Problem	Language	Result	Execution time	Memory
826296		Sohsoh84	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	229 ms	28188 KiB

railroad

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)		(x).begin(), (x).end()
#define debug(x)	cerr << #x << ": " << x << endl;
#define sep		' '
#define X		first
#define Y		second

const ll MAXN = 1e6 + 10;
const ll INF = 1e9 + 7;

int n, cnt[MAXN], par[MAXN];
vector<int> comp_vec;
ll k;
int find(int v) {
	return par[v] == v ? v : par[v] = find(par[v]);
}

inline bool unite(int u, int v) {
	int u_ = u, v_ = v;
	u = find(u), v = find(v);
	if (u == v) return false;
	par[u] = v;
	
//	cerr << "unite: " << u_ << " " << v_ << endl;
	return true;
}

inline int ind(int x) {
	return lower_bound(all(comp_vec), x) - comp_vec.begin();
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
	s.push_back(0);
	t.push_back(1e9 + 7);

	ll ans = 0;
	for (int i = 0; i < int(s.size()); i++) {
		comp_vec.push_back(s[i]);
		comp_vec.push_back(t[i]);
		k += t[i] - s[i];
	}

	sort(all(comp_vec));
	comp_vec.resize(unique(all(comp_vec)) - comp_vec.begin());


	int m = comp_vec.size();
	for (int i = 0; i < m; i++) par[i] = i;

	k -= 1e9 + 7;
	for (int i = 0; i < int(s.size()); i++) {
		cnt[ind(s[i])]++;
		cnt[ind(t[i])]--;
		unite(ind(s[i]), ind(t[i]));
	}


	int tot = -1;
	vector<pair<int, pll>> edges;
	for (int i = 0; i < m - 1; i++) {
		tot += cnt[i];
		if (tot <= 0) {
			//ans += 1ll * (1 - tot) * (comp_vec[i + 1] - comp_vec[i]);
			unite(i, i + 1);
		} else if (tot > 1) {
			unite(i, i + 1);
			ans += 1ll * (tot - 1) * (comp_vec[i + 1] - comp_vec[i]);
		}

		//cerr << tot << sep << comp_vec[i] << sep << ans << endl;
		edges.push_back({comp_vec[i + 1] - comp_vec[i], {i, i + 1}});
	}

	sort(all(edges));
	for (auto [x, e] : edges)
		if (unite(e.X, e.Y)){
		//	cerr << e.X << ' ' << e.Y << ' ' <<  x << endl;
			ans += x;
		}

	return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'bool unite(int, int)':
railroad.cpp:26:6: warning: unused variable 'u_' [-Wunused-variable]
   26 |  int u_ = u, v_ = v;
      |      ^~
railroad.cpp:26:14: warning: unused variable 'v_' [-Wunused-variable]
   26 |  int u_ = u, v_ = v;
      |              ^~

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