Submission #332149

#	Time	Username	Problem	Language	Result	Execution time	Memory
332149		LifeHappen__	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	54 ms	3436 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define all(a) a.begin(),a.end()
#define lli long long
using namespace std;
 
const int N = 2e5+5;
int n, s[N], t[N];
int in[N], out[N];
lli that[N], res;
 
struct DSU{
	int n;
	vector<int> id;
	DSU(int n) : n(n), id(n+1,-1){}
	int root(int u){
		return id[u]<0 ? u : id[u]=root(id[u]);
	}
	bool join(int u,int v){
		if((u=root(u))==(v=root(v))) return 0;
		if(id[u]>id[v]) swap(u,v);
		id[u] += id[v];
		id[v] = u;
		return 1;
	}
};
 
struct edge{
	int u, v;
	lli c;
};
vector<edge> E;
 
long long plan_roller_coaster(vector<int> s,vector<int> t){
	vector<int> rrh;
	forinc(i,0,n - 1){
		rrh.push_back(s[i]);
		rrh.push_back(t[i]);
	}
	sort(all(rrh));
	rrh.erase(unique(all(rrh)),rrh.end());
	int ma = rrh.size();
	DSU dsu(ma);
	forinc(i,0,n - 1){
		int _s = lower_bound(all(rrh),s[i]) - rrh.begin() + 1;
		int _t = lower_bound(all(rrh),t[i]) - rrh.begin() + 1;
		that[_s] = s[i], that[_t] = t[i];
		out[_s]++; in[_t]++;
		dsu.join(_s,_t);
	}
	out[ma]++; in[1]++;
	fordec(i,ma,1) {
		if(in[i] > out[i]){
			in[i-1] += in[i]-out[i];
			res += 1ll*(in[i]-out[i])*(that[i]-that[i-1]);
			dsu.join(i-1,i);
		}
		else if(in[i] < out[i]){
			out[i-1] += out[i] - in[i];
			dsu.join(i-1,i);
		}
	}
	forinc(i,1,ma-1) if(dsu.root(i) != dsu.root(i+1))
		E.push_back({i,i+1,that[i+1]-that[i]});
	sort(all(E),[](const edge &a, const edge &b){
		return a.c < b.c;
	});
	for(edge e:E) {
		if(dsu.join(e.u, e.v)) res += e.c;
	}
	return res;
}

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