Submission #825792

#	Time	Username	Problem	Language	Result	Execution time	Memory
825792		tomruk	Sky Walking (IOI19_walk)	C++17	24 / 100	4121 ms	612444 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
map<int,vector<int>> adj[N];
map<int,long long> d[N];
long long min_distance(vector<int> p, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	int n = p.size();
	int m = l.size();
	vector<pair<int,int>> v;
	for(int i = 0;i<n;i++){
		v.push_back({h[i],i});
		adj[i][0].push_back(i);
	}
	for(int i = 0;i<m;i++){
		v.push_back({y[i],~i});
	}
	sort(v.rbegin(),v.rend());
	set<int> active;
	for(auto u:v){
		if(u.second < 0){
			u.second = ~u.second;
			auto it = active.lower_bound(l[u.second]);
			while(1){
				auto it2 = it;
				it2++;
				if(it2 == active.end() || *it2 > r[u.second])
					break;
				adj[*it][y[u.second]].push_back(*it2);
				adj[*it2][y[u.second]].push_back(*it);
				it = it2;
			}
		}
		else{
			active.insert(u.second);
		}
	}
	priority_queue<pair<long long,pair<int,int>>> q;
	d[s][0] = 0;
	q.push({-d[s][0],{s,0}});
	while(q.size()){
		auto tp = q.top();
		q.pop();
		tp.first *= -1;
		int x = tp.second.first;
		int y = tp.second.second;
		if(tp.first != d[x][y])
			continue;
		// cout << x << ' ' << y << endl;
		// cout << tp.first << endl;
		for(auto u:adj[x][y]){
			long long nw = abs(p[x] - p[u]) + tp.first;
			if(d[u].count(y) == 0 || d[u][y] > nw){
				d[u][y] = nw;
				q.push({-d[u][y],{u,y}});
			}
		}
		auto it = adj[x].find(y);
		if(next(it) != adj[x].end()){
			long long nw = abs(y - next(it)->first) + tp.first;
			if(d[x].count(next(it)->first) == 0 || d[x][next(it)->first] > nw){
				d[x][next(it)->first] = nw;
				q.push({-d[x][next(it)->first],{x,next(it)->first}});
			}
		}
		if(it != adj[x].begin()){
			long long nw = abs(y - prev(it)->first) + tp.first;
			if(d[x].count(prev(it)->first) == 0 || d[x][prev(it)->first] > nw){
				d[x][prev(it)->first] = nw;
				q.push({-d[x][prev(it)->first],{x,prev(it)->first}});
			}
		}
	}
	return (d[g].count(0)?d[g][0]:-1);
}

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