Submission #332180

#	Time	Username	Problem	Language	Result	Execution time	Memory
332180		nouvo25	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	232 ms	16472 KiB

railroad

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define io ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
 
using namespace std;
 
const int MAXN = 4e5 + 7;
 
int s[MAXN], t[MAXN], n, in[MAXN], out[MAXN], fa[MAXN];
vector<int> val;
 
void change(int &n)
{
	n = lower_bound(val.begin(), val.end(), n) - val.begin();
}
 
int root(int u)
{
	if (fa[u] < 0) return u;
	return fa[u] = root(fa[u]);
}
 
void join(int u, int v)
{
	u = root(u), v = root(v);
	if (u != v) fa[u] = v;
}
 
ll plan_roller_coaster(vector<int> s, vector<int> t)
//int main()
{
//	freopen("test.INP","r",stdin);
//	freopen("BAILAM.OUT","w",stdout);
//	io;
	n = (int)s.size();
//	cin >> n;
	for (int i = 0; i < n; ++i) 
	{
//		cin >> s[i] >> t[i];
		val.push_back(s[i]);
		val.push_back(t[i]);
	}
	sort(val.begin(), val.end());
	val.erase(unique(val.begin(), val.end()), val.end());
	
	int sz = (int)val.size();
	for (int i = 0; i < sz; ++i) fa[i] = -1;
	++out[sz - 1], ++in[0];
	join(0, sz - 1);
	for (int i = 0; i < n; ++i)
	{
		change(s[i]);
		change(t[i]);
		++out[s[i]], ++in[t[i]];
		join(s[i], t[i]);
	}
	
	vector< pair<int, pair<int,int> > > ed;
	ll res = 0;
	for (int i = sz - 1; i > 0; --i)
	{
		if (out[i] != in[i]) 
		{
			join(i, i - 1);
			if (out[i] > in[i]) out[i - 1] += (out[i] - in[i]);
			else in[i - 1] += (in[i] - out[i]), res += 1LL * (val[i] - val[i - 1]) * (in[i] - out[i]);
		}else ed.push_back({val[i] - val[i - 1], {i, i - 1}});
	}
//	cout << res << '\n';
	sort(ed.begin(), ed.end());
	for (auto it: ed)
	{
		int u = root(it.se.fi), v = root(it.se.se), cost = it.fi;
		if (u != v)
		{
			res += cost;
			fa[u] = v;
		}
	}
//	cout << res;
//	return 0;
	return res;
}

//int main()
//{
//	return 0;
//}

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