Submission #650017

#	Time	Username	Problem	Language	Result	Execution time	Memory
650017		jamezzz	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	168 ms	22820 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
#define fi first
#define se second
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
#define maxn 200005
#define INF 1023456789
#define LINF 1023456789123456789

int par[maxn],rnk[maxn];
vector<pair<int,ii>> pts,edges;

int fp(int i){return par[i]==i?i:par[i]=fp(par[i]);}
bool join(int x,int y){
	x=fp(x),y=fp(y);
	if(x==y)return false;
	if(rnk[x]<rnk[y])par[x]=y;
	else par[y]=x;
	if(rnk[x]==rnk[y])++rnk[x];
	return true;
}

ll plan_roller_coaster(vi s,vi t){
	int n=s.size();
	for(int i=0;i<n;++i){
		pts.pb({s[i],{1,i}});
		pts.pb({t[i],{-1,i}});
	}
	pts.pb({INF,{1,n}});
	pts.pb({1,{-1,n}});
	++n;
	for(int i=0;i<n;++i)par[i]=i;
	sort(all(pts));
	ll ans=0;
	int cur=0;
	for(int i=0;i<pts.size()-1;++i){
		cur+=pts[i].se.fi;
		ans+=(ll)max(cur,0)*(pts[i+1].fi-pts[i].fi);
		edges.pb({pts[i+1].fi-pts[i].fi,{pts[i].se.se,pts[i+1].se.se}});
		if(pts[i].fi==pts[i+1].fi||cur!=0)join(pts[i].se.se,pts[i+1].se.se);
	}
	sort(all(edges));
	for(int i=0;i<edges.size();++i){
		if(join(edges[i].se.fi,edges[i].se.se))ans+=edges[i].fi;
	}
	return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'll plan_roller_coaster(vi, vi)':
railroad.cpp:43:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i=0;i<pts.size()-1;++i){
      |              ~^~~~~~~~~~~~~
railroad.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i=0;i<edges.size();++i){
      |              ~^~~~~~~~~~~~~

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