Submission #424756

#	Time	Username	Problem	Language	Result	Execution time	Memory
424756		Kevin_Zhang_TW	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	218 ms	12768 KiB

railroad

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;
const ll inf = 1ll << 55;
#include "railroad.h"

struct dsu {
	vector<int> g;
	int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
	int operator()(int i) { return F(i); }
	bool M(int a, int b) {
		a = F(a), b = F(b);
		if (a == b) return false;
		return g[b] = a, true;
		//return g[F(b)] = F(a), F(a) != F(b);
	}
	dsu(int n) { g.resize(n + 10), iota(AI(g), 0); }
};
struct lisan : vector<int> {
	void done() { sort(AI()), erase(unique(AI()), end()); }
	int operator ()(int i) {
		return lower_bound(AI(), i) - begin(); 
	}
};

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size() + 1;

	s.pb(1e9);
	t.pb(1);

	lisan lis;
	for (int i = 0;i < n;++i) {
		lis.pb(s[i]), lis.pb(t[i]);
	}
	lis.done();

	int m = lis.size();
	for (int i = 1;i < m;++i) assert(lis[i] > lis[i-1]);

	dsu D(m);

	vector<int> pf(m + 10), suf(m + 10);
	for (int i = 0;i < n;++i) {
		int a = lis(s[i]), b = lis(t[i]);
		D.M(a, b);

		++pf[a], --pf[b];

		assert(a < m && b < m);
	}
	for (int i = 1;i <= m;++i) pf[i] += pf[i-1];

	ll res = 0;

	for (int i = 0;i < m;++i) {
		if (pf[i] != 0) {
			assert(i+1 < m);
			D.M(i, i+1);
			res += max(0, pf[i]) * 1ll * (lis[i+1] - lis[i]);
		}
	}

	vector<pair<int,int>> alle;

	for (int i = 0;i+1 < m;++i) if (D(i) != D(i+1)) {
		alle.pb(lis[i+1] - lis[i], i);
	}

	sort(AI(alle));
	for (auto [w, i] : alle)
		if (D.M(i, i+1))
			res += w;

	return res;
}

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