Submission #986391

#	Time	Username	Problem	Language	Result	Execution time	Memory
986391		Pyqe	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	121 ms	36908 KiB

railroad

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

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long ma=1e9;
long long n,dsu[400069];
pair<long long,pair<long long,long long>> as[400069],ed[400069];
pair<long long,long long> pst[200069];

long long fd(long long x)
{
	if(dsu[x]!=x)
	{
		dsu[x]=fd(dsu[x]);
	}
	return dsu[x];
}

long long plan_roller_coaster(vector<int> ka,vector<int> la)
{
	long long i,k,l,w,c=0,z=0;
	
	n=ka.size()+1;
	for(i=1;i<=n;i++)
	{
		if(i<n)
		{
			k=ka[i-1];
			l=la[i-1];
		}
		else
		{
			k=ma+1;
			l=0;
		}
		z+=l-k;
		as[i*2-1]={k,{i,1}};
		as[i*2]={l,{i,-1}};
	}
	sort(as+1,as+n*2+1);
	for(i=1;i<=n*2;i++)
	{
		k=as[i].fr;
		l=as[i].sc.fr;
		w=as[i].sc.sc;
		z+=(k-as[i-1].fr)*abs(c);
		dsu[i]=i;
		if(c)
		{
			dsu[fd(i-1)]=fd(i);
		}
		c+=w;
		pst[l].fr=i;
		swap(pst[l].fr,pst[l].sc);
	}
	for(i=1;i<=n;i++)
	{
		k=pst[i].fr;
		l=pst[i].sc;
		dsu[fd(l)]=fd(k);
	}
	for(i=1;i<n*2;i++)
	{
		ed[i]={(as[i+1].fr-as[i].fr)*2,{fd(i),fd(i+1)}};
	}
	sort(ed+1,ed+n*2);
	for(i=1;i<n*2;i++)
	{
		w=ed[i].fr;
		k=ed[i].sc.fr;
		l=ed[i].sc.sc;
		z+=w*(fd(k)!=fd(l));
		dsu[fd(l)]=fd(k);
	}
	z/=2;
	return z;
}

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