Submission #1167300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167300		hyakup	Sky Walking (IOI19_walk)	C++20	10 / 100	4094 ms	1082072 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int A, int B) {
	int n = x.size(), m = l.size();
	int cont = 0;
	vector<vector<pair<ll, ll>>> adj;
	multiset<pair<ll, ll>> s[n];

	auto create  = [&]( int id, int alt ){

		// cout << "+ " << id << " " << alt << endl;

		s[id].insert({ alt, cont });
		adj.emplace_back();
		return cont++;
	};

	for( int i = 0; i < m; i++ ){
		ll last = -1;
		ll pos = -1;
		for( int j = l[i]; j <= r[i]; j++ ) if( y[i] <= h[j] ){
			int a = create( j, y[i] );
			// cout << a << " " << last << endl;
			if( last != -1 ){
				adj[a].push_back({ last, x[j] - pos });
				adj[last].push_back({ a, x[j] - pos });
			}
			last = a;
			pos = x[j];
		}
	}

	vector<int> v(n);

	for( int i = 0; i < n; i++ ){
		int last = -1;
		int pos = -1;
		v[i] = create( i, 0 );
		for( auto [alt, a] : s[i] ){
			// cout << a << " " << last << " " << alt - pos << endl;
			if( last != -1 ){
				adj[a].push_back({ last, alt - pos });
				adj[last].push_back({ a, alt - pos });
			}
			last = a;
			pos = alt;
		}
	}

	vector<ll> dist(cont, 1e18);
	auto dijkstra = [&]( int source ){
		set<pair<ll, ll>> ss;
		ss.insert({ 0, source });
		dist[source] = 0;
		while( !ss.empty() ){
			int cur = ss.begin()->second; ss.erase(ss.begin());
			// cout << "    " << cur << "  " << dist[cur] << endl;
			for( auto [viz, d] : adj[cur] ) if( dist[viz] > dist[cur] + d ){
				ss.erase({ dist[viz], viz });
				dist[viz] = dist[cur] + d;
				ss.insert({ dist[viz], viz });
			}
		}
	};

	dijkstra( v[A] );
	if( dist[v[B]] == 1e18 ) dist[v[B]] = -1; 
	return dist[v[B]];


}

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