Submission #602875

#	Time	Username	Problem	Language	Result	Execution time	Memory
602875		8e7	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	117 ms	19792 KiB

railroad

#include "railroad.h"
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 400005
#define pii pair<int, int>
#define ff first
#define ss second
const ll inf = 1LL<<60;
struct DSU{
	int par[maxn];
	void init(int n){
		for (int i = 0;i <= n;i++) par[i] = i;
	}
	int find(int a){
		return a == par[a] ? a : (par[a] = find(par[a]));
	}
	bool Union(int a, int b){
		a = find(a), b = find(b);
		if (a == b) return 0;
		par[a] = b;
		return 1;
	}
} dsu;

struct obj{
	int pos, val, id;
	obj(){pos = val = id = 0;}
	obj(int a, int b, int c){pos = a, val = b, id = c;}
};
int vis[maxn];
long long plan_roller_coaster(std::vector<int> S, std::vector<int> T) {
    int n = (int) S.size();
	vector<obj> a, ed;
	for (int i = 0;i < n;i++) {
		a.push_back(obj(S[i], 1, i));
		a.push_back(obj(T[i], -1, i));
	}
	a.push_back(obj(1<<30, 1, n));
	a.push_back(obj(1, -1, n));
	sort(a.begin(),a.end(), [&] (obj x, obj y){return x.pos < y.pos;});

	int siz = 2*n + 2;
	dsu.init(siz);
	
	ll cur = 0, x = 1;
	ll ans = 0;
	int ind = 0;
	for (auto [pos, val, id]:a) {
		if (cur != 0) {
			ans += max(cur, 0LL) * (pos - x);	
			dsu.Union(ind, ind-1);	
		} else if (ind){
			ed.push_back(obj(ind, ind-1, pos - x));
		}
		x = pos;
		cur += val;
		if (vis[id]) {
			dsu.Union(ind, vis[id]-1);
		} else {
			vis[id] = ind+1;
		}
		ind++;
	}
	debug(ans);
	sort(ed.begin(), ed.end(), [&] (obj x, obj y){return x.id < y.id;});
	for (auto [u, v, w]:ed) {
		if (dsu.Union(u, v)) ans += w;
	}	
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
railroad.cpp:77:2: note: in expansion of macro 'debug'
   77 |  debug(ans);
      |  ^~~~~

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