Submission #182394

#	Time	Username	Problem	Language	Result	Execution time	Memory
182394		CaroLinda	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	1216 ms	131588 KiB

railroad

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

#define debug printf
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define ll long long
#define sz size()
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define tiii tuple<int,int,int>
#define mkt make_tuple

const int MAXN = 2e5+10 ;
const ll inf = 1e18+10 ;

using namespace std ;

int n , Key , comp ;
int bit[MAXN*2] , realVal[MAXN*2] , myComp[MAXN*2] , pai[MAXN*2] ;
map<int,int> mp ;
vector<int> adj[MAXN*2] ;
ll ans ;
bool vis[MAXN*2] ;
vector< tuple<int,int,int> > edges ;
set<int> thereIsConnection[MAXN*2] ;

void upd(int pos, int val) { for(int i = pos ; i < MAXN*2 ; i += (i&-i) ) bit[i] += val ; }
int qry(int pos)
{
	int tot = 0 ;
	for(int i = pos ; i > 0 ; i -= (i&-i) )
		tot += bit[i] ;
	return tot;
}

void dfs(int cur)
{

	myComp[cur] = comp ;
	vis[cur] = true ;

	for(int viz : adj[cur])
		if(!vis[viz])
			dfs(viz) ;

}

int find(int i)
{
	if( pai[i] == i ) return i ;
	return pai[i] = find(pai[i]);
}

void join(int a, int b,int cost)
{
	a = find(a) ;
	b = find(b) ;
	if(a == b) return ;
	ans += 1LL * cost ;
	if( rand()%2 ) pai[a] = b ;
	else pai[b] = a ;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) 
{
    n = (int)(s.sz);

    for(int i : s ) mp[i] = 0 ;
    for(int i : t ) mp[i] = 0 ;

    for(auto &p : mp ) 
    {
    	p.ss = ++Key ;
    	realVal[Key] = p.ff ;
    }

	int val1,val2;
	lp(i,0,n)
	{
		s[i] = mp[ s[i] ] ;
		t[i] = mp[ t[i] ] ;

		if( s[i] == t[i] ) continue ;

		thereIsConnection[ s[i] ].insert(t[i]) ;

		if( s[i] > t[i] ) 
		{
			upd( t[i] , -1 ) ;
			upd( s[i], 1 ) ;
			continue ;
		}

		upd( s[i] , 1 ) ;
		upd( t[i], -1 ) ;

	}
	upd(1,-1) ;
	upd( Key, 1 ) ;
	thereIsConnection[Key].insert(1) ;

	lp(i,1,Key)
	{

		int val = qry(i) ;

		if(val != 0)
		{
			thereIsConnection[i].insert(i+1) ;
			thereIsConnection[i+1].insert(i) ;
		}

		if( val > 0 )
			ans += 1LL*val*(realVal[i+1]-realVal[i]) ;

	}

	lp(i,1,Key)
		for(auto p : thereIsConnection[i]) adj[i].pb(p) ;

	lp(i,1,Key+1)
		if( !vis[i] )
		{
			comp ++ ;
			dfs(i) ;
		}

	lp(i,1,Key)
		if( myComp[i] != myComp[i+1] )
			edges.pb( mkt( realVal[i+1] - realVal[i] , myComp[i] , myComp[i+1] ) ) ;

	sort(all(edges)) ;
	lp(i,1,comp+1) pai[i] = i ;

	for(auto p : edges)
		join( get<1>(p) , get<2>(p) , get<0>(p) ) ;

    return ans ;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:81:6: warning: unused variable 'val1' [-Wunused-variable]
  int val1,val2;
      ^~~~
railroad.cpp:81:11: warning: unused variable 'val2' [-Wunused-variable]
  int val1,val2;
           ^~~~

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