Submission #592650

#	Time	Username	Problem	Language	Result	Execution time	Memory
592650		Lucpp	Sky Walking (IOI19_walk)	C++17	24 / 100	4073 ms	220480 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
typedef long long ll;
const ll INF = 1e18;

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int start, int goal) {
	int n = (int)X.size(), m = (int)L.size();
	vector<vector<int>> sect(n, {0});
	vector<vector<pair<int, int>>> goL(n, {{-1, -1}}), goR(n, {{-1, -1}});
	vector<tuple<int, int, int>> bridge;
	for(int i = 0; i < m; i++) bridge.emplace_back(Y[i], L[i], R[i]);
	sort(bridge.begin(), bridge.end());
	vector<pair<int, int>> tower;
	for(int i = 0; i < n; i++) tower.emplace_back(H[i], i);
	sort(tower.begin(), tower.end());
	set<int> active;
	for(int i = 0; i < n; i++) active.insert(i);
	int j = 0;
	for(auto [y, l, r] : bridge){
		while(j < n && tower[j].first < y) active.erase(tower[j++].second);
		auto it = active.find(l);
		int last = -1;
		while(it != active.end() && *it <= r){
			sect[*it].push_back(y);
			goL[*it].push_back({-1, -1});
			goR[*it].push_back({-1, -1});
			if(last != -1) goR[last].back() = {*it, sz(sect[*it])-1}, goL[*it].back() = {last, sz(sect[last])-1};
			last = *it;
			it++;
		}
	}
	map<pair<int, int>, ll> dist;
	priority_queue<tuple<ll, int, int>> pq;
	dist[make_pair(start, 0)] = 0;
	pq.emplace(0, start, 0);
	auto visit = [&](int x, int h, ll d){
		auto p = make_pair(x, h);
		if(!dist.count(p) || d < dist[p]){
			dist[p] = d;
			pq.emplace(-d, x, h);
		}
	};
	while(!pq.empty()){
		auto [d, x, h] = pq.top();
		pq.pop();
		d = -d;
		if(d > dist[make_pair(x, h)]) continue;
		if(goL[x][h].first != -1) visit(goL[x][h].first, goL[x][h].second, d+X[x]-X[goL[x][h].first]);
		if(goR[x][h].first != -1) visit(goR[x][h].first, goR[x][h].second, d+X[goR[x][h].first]-X[x]);
		if(h > 0) visit(x, h-1, d+sect[x][h]-sect[x][h-1]);
		if(h < sz(sect[x])-1) visit(x, h+1, d+sect[x][h+1]-sect[x][h]);
	}
	if(!dist.count(make_pair(goal, 0))) return -1;
	else return dist[make_pair(goal, 0)];
}

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