Submission #208029

#	Time	Username	Problem	Language	Result	Execution time	Memory
208029		Lawliet	Sky Walking (IOI19_walk)	C++17	24 / 100	2126 ms	1048576 KiB

walk

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

using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;

const int MAXN = 2000010;
const lli INF = 1000000000000000000LL;

int n, m;
int cntNode;

lli dist[MAXN];

vector< int > adj[MAXN];
vector< int > weight[MAXN];

vector< int > sweep[MAXN];
vector< int > building[MAXN];
vector< int > intersection[MAXN];

map< int , int > indNode[MAXN];

void buildEdge(int U, int V, int W)
{
	adj[U].push_back( V );
	adj[V].push_back( U );

	weight[U].push_back( W );
	weight[V].push_back( W );
}

void Dijkstra(int S)
{
	set< pair<lli,int> > s;

	for(int i = 1 ; i <= cntNode ; i++)
		dist[i] = INF;

	dist[S] = 0;
	s.insert( { 0 , S } );

	while( !s.empty() )
	{
		int cur = s.begin()->second;
		s.erase( s.begin() );

		for(int i = 0 ; i < (int) adj[cur].size() ; i++)
		{
			int viz = adj[cur][i];
			int w = weight[cur][i];

			if( dist[viz] > dist[cur] + w )
			{
				s.erase( { dist[viz] , viz } );
				dist[viz] = dist[cur] + w;
				s.insert( { dist[viz] , viz } );
			}
		}
	}
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int a, int b) 
{
	n = x.size(); m = l.size();

	for(int i = 0 ; i < m ; i++)
	{
		sweep[ l[i] ].push_back( i + 1 );
		sweep[ r[i] + 1 ].push_back( -i - 1 );
	}

	set< pii > s;

	for(int i = 0 ; i < n ; i++)
	{
		indNode[i][0] = ++cntNode;
		building[i].push_back( 0 );

		while( !sweep[i].empty() )
		{
			int cur = sweep[i].back();
			sweep[i].pop_back();

			if( cur > 0 ) s.insert( { y[cur - 1] , cur - 1 } );
			else s.erase( { y[-cur - 1] , -cur - 1 } );
		}

		for(auto it = s.begin() ; it != s.end() ; it++)
		{
			int curY = it->first;
			int curSkyWalking = it->second;

			if( curY > h[i] ) break;

			indNode[i][curY] = ++cntNode;
			buildEdge( cntNode - 1 , cntNode , curY - building[i].back() );

			building[i].push_back( curY );

			intersection[ curSkyWalking ].push_back( i );
		}
	}

	for(int i = 0 ; i < m ; i++)
	{
		for(int j = 0 ; j < (int) intersection[i].size() - 1 ; j++)
		{
			int U = intersection[i][j];
			int V = intersection[i][j + 1];
			int W = x[V] - x[U];

			U = indNode[U][ y[i] ];
			V = indNode[V][ y[i] ];

			buildEdge( U , V , W );
		}
	}

	int S = indNode[a][0];
	int T = indNode[b][0];

	Dijkstra( S );

	if( dist[T] == INF ) return -1;
	return dist[T];
}

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