Submission #205200

#	Time	Username	Problem	Language	Result	Execution time	Memory
205200		puppies_and_rainbows	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	142 ms	11420 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"

using namespace std;

pair<long long, long long> a[200005], b[200005];
long long f[200005], n, tot;

long long find(long long i)
{
	return f[i]==i? f[i]:f[i]=find(f[i]);
}

void unionn(long long i, long long j)
{
	f[find(i)]=find(j);
	tot--;
}

long long plan_roller_coaster(vector<int> s, vector<int> t)
{
	s.push_back(1000000000);
	t.push_back(1);
	n=s.size(), tot=n;
	for(long long i=1; i<=n; i++)
	{
		f[i]=i;
		a[i]={s[i-1], i};
		b[i]={t[i-1], i};
	}
	sort(a+1, a+n+1);
	sort(b+1, b+n+1);
	for(long long i=1; i<=n; i++)
	{
		if(a[i].first<b[i].first) return 178;
		unionn(a[i].second, b[i].second);
	}
	for(long long i=1; i<n; i++)
	{
		if(find(a[i].second)!=find(a[i+1].second))
		{
			if(a[i].first>b[i+1].first)
			{
				unionn(a[i].second, a[i+1].second);
			}
		}
	}
	if(tot==1) return 0;
	else return 2;
}

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