Submission #170717

#	Time	Username	Problem	Language	Result	Execution time	Memory
170717		dennisstar	Roller Coaster Railroad (IOI16_railroad)	C++11	100 / 100	404 ms	48232 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;

int par[400010], deg[400010], chk[400010];
int get(int i) {
	if (par[i]==i) return i;
	else return par[i]=get(par[i]);
}
vim V[400010], cp;
int N, M, tp;
ll ans;

void dfs(int now, int num) {
	chk[now]=num;
	for (int i:V[now]) if (!chk[i]) dfs(i, num);
}

ll plan_roller_coaster(vim s, vim t) {
	N=s.size();

	//coordinate compression
	for (int i:s) cp.push_back(i);
	for (int i:t) cp.push_back(i);
	sort(all(cp)); cp.erase(unique(all(cp)), cp.end()); M=cp.size();
	vim S, T;
	S.push_back(0); T.push_back(0);
	for (int i:s) {
		int lb=lower_bound(all(cp), i)-cp.begin();
		S.push_back(lb+1);
		deg[lb+1]++;
	}
	for (int i:t) {
		int lb=lower_bound(all(cp), i)-cp.begin();
		T.push_back(lb+1);
		deg[lb+1]--;
	}

	//generate edges
	for (int i=1; i<=N; i++) V[S[i]].push_back(T[i]);
	for (int i=1; i<M; i++) {
		int req=(i==1?1:0);
		int now=req-deg[i];
		if (now>0) {
			deg[i]+=now;
			deg[i+1]-=now;
			V[i].push_back(i+1);
		}
		else if (now<0) { 
			deg[i]+=now;
			deg[i+1]-=now;
			V[i+1].push_back(i);
			ans+=(ll)abs(now)*(cp[i]-cp[i-1]);
		}
	}

	//mst
	for (int i=1; i<M; i++) if (!chk[i]) dfs(i, ++tp);
	for (int i=1; i<=tp; i++) par[i]=i;
	vector<pii> e;
	for (int i=1; i<M; i++) if (chk[i]!=chk[i+1]) e.push_back({cp[i]-cp[i-1], i});
	sort(all(e));
	for (pii pi:e) {
		int x1=get(chk[pi.se]), x2=get(chk[pi.se+1]);
		if (x1!=x2) {
			ans+=(ll)pi.fi;
			par[x2]=x1;
		}
	}

	return ans;
}

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