제출 #332162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332162		nouvo25	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	200 ms	10412 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)
{
//	freopen("test.INP","r",stdin);
//	freopen("BAILAM.OUT","w",stdout);
//	io;
	n = (int)s.size();
	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]);
	}
	
//	ll res = 0;
//	for (int i = sz - 1; i > 0; --i)
//	{
//		while (out[i] > in[i]) ++in[i], ++out[i - 1], join(i, i - 1);
//		while (out[i] < in[i]) ++out[i], ++in[i - 1], join(i, i - 1), res += (val[i] - val[i - 1]);
//	}
//	
//	vector< pair<int, pair<int,int> > > ed;
//	for (int i = 0; i < sz - 1; ++i) ed.push_back({val[i + 1] - val[i], {i, i + 1}});
////	for (int i = 0; i < sz; ++i) cout << i << ' ' << val[i] << ' ' << root(i) << '\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;
}

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