Submission #424685

#	Time	Username	Problem	Language	Result	Execution time	Memory
424685		Kevin_Zhang_TW	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	191 ms	12280 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, sz;
	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;
		if (sz[a] < sz[b]) swap(a, b);
		return sz[a] += sz[b], g[b] = a, true;
	}
	dsu(int n) {
		g.resize(n + 10), sz.resize(n + 10, 1);
		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(*max_element(AI(s)) + 10);
	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();

	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);
		if (a <= b) 
			++pf[a], --pf[b];
		else 
			++suf[b], --suf[a];
		assert(a < m && b < m);
	}
	for (int i = 1;i < m;++i) pf[i] += pf[i-1];
	for (int i = m-1;i >= 0;--i) suf[i] += suf[i+1];

	ll res = 0;

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

	for (int i = 0;i < m;++i) {
		if (D(i) != D(0)) return 1;
	}

	return res;
}

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