Submission #285375

#	Time	Username	Problem	Language	Result	Execution time	Memory
285375		CaroLinda	Sky Walking (IOI19_walk)	C++14	24 / 100	4128 ms	723012 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

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

const int MAX = 1e7+10 ;
const ll inf = 1e18+10 ;

using namespace std ;

struct Event
{
	int type , h , id ;
	Event(int type = 0 ,int h = 0 ,int id = 0 ) : type(type) , h(h) , id(id) {}
	bool operator < ( Event other ) const 
	{
		if(h == other.h) return type < other.type ;
		return h > other.h ;
	}
} ;

int N , M ;
vector<pii> numX[MAX] ;
vector<Event> sweep ;
map< pii , int > mp ;
set<int> s ;
vector<pii> adj[MAX] ;
ll dist[MAX] ;

void dijkstra(int S)
{

	lp(i,1,sz(mp)+1) dist[i] = inf ;
	dist[ S ] = 0 ;

	priority_queue< pair<ll,int> , vector< pair<ll,int> > , greater< pair<ll,int> > > fila ;
	fila.push( mk(0,S) ) ;

	while(!fila.empty())
	{
		int x = fila.top().ss ;
		ll d = fila.top().ff ;

		fila.pop() ;

		if(d != dist[x]) continue ;


		for(auto e : adj[x] ) 
		{
			ll dd = d + (ll)e.ss ;

			if( dd >= dist[e.ff] ) continue ;

			dist[e.ff] = dd;
			fila.push(mk(dd, e.ff) ) ;

		}

	}
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int S, int G) 
{
	
	N = sz(h) ;
	M = sz(l) ;

	lp(i,0,N) 
	{
		mp.insert( mk( mk(i , 0)  , sz(mp) + 1) ) ;
		sweep.pb( Event(0 , h[i] , i) ) ;
	}

	lp(i,0,M) sweep.pb( Event(1, y[i] , i ) ) ;

	sort(all(sweep)) ;

	for(auto e : sweep )
	{
		if(e.type == 0) 
		{
			s.insert(e.id) ;
			continue ;
		}

		auto L = s.find( l[e.id] ) ;
		auto R = s.find( r[e.id] ) ;

		vector<int> aux ;

		while( true )
		{

			if( mp.find( mk( *L , e.h ) ) == mp.end() )
				mp.insert( mk(mk(*L , e.h) , sz(mp) + 1) ) ;

			aux.pb( *L ) ;

			if(L == R) break ;
			L++ ;
		}


		for(int i = 0 ; i < sz(aux) - 1 ; i++ )
		{
			int id1 = aux[i] ;
			int id2 = aux[i+1] ;

			int a1 = mp[mk(id1, e.h) ] ;
			int a2 = mp[mk(id2, e.h) ] ;

			adj[a1].pb( mk( a2, x[id2] - x[id1] ) ) ;
			adj[ a2 ].pb( mk( a1, x[id2] - x[id1] ) ) ;
 		}

	}

	for(auto e : mp ) numX[ e.ff.ff ].pb( mk( e.ff.ss, e.ss ) ) ;

	lp(i,0,N)
		for(int j = 1 ; j < sz(numX[i]) ; j++ )
		{
			int dist = numX[i][j].ff - numX[i][j-1].ff ;
			adj[ numX[i][j-1].ss ].pb(mk( numX[i][j].ss , dist ) );
			adj[ numX[i][j].ss ].pb(mk( numX[i][j-1].ss , dist ) );
		}

	
	S = mp[ mk(S,0) ] ;
	G = mp[ mk(G,0) ] ;

	dijkstra(S) ;

	return dist[ G ] == inf ? -1 : dist[G] ;
	
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43