제출 #361135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361135		tengiz05	Sky Walking (IOI19_walk)	C++17	10 / 100	4094 ms	4644 KiB

walk

#include "walk.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
map<pair<ll,ll>, ll> d;
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	n = x.size(); m = l.size();
	priority_queue<tuple<ll,ll,ll>,vector<tuple<ll,ll,ll>>,greater<tuple<ll,ll,ll>>> q;
	q.push(make_tuple(0,x[s],0));
	d[{x[s],0}] = 0;
	while(!q.empty()){
		auto [dist, X, Y] = q.top(); q.pop();
		//~ if(dist > d[{X,Y}])continue;
		//~ cout << dist << '\t' << X << ' ' << Y << '\n';
		ll id = lower_bound(x.begin(),x.end(),X) - x.begin();
		if(X != x[s] && Y == 0)continue;
		ll f=0;
		for(int i=0;i<m;i++){
			if(l[i] <= id && r[i] >= id && y[i] == Y)f = i;
			if(l[i] > id || r[i] < id || h[id] < y[i])continue;
			if(h[id] >= Y && (!d.count({X,y[i]}) || d[{X,y[i]}] > dist+abs(Y - y[i]))){
				d[{X,y[i]}] = dist+abs(Y - y[i]);
				q.push(make_tuple(dist+abs(Y - y[i]), X, y[i]));
			}
			if(y[i] == Y){
				if(id != l[i] && (!d.count({x[id-1],Y}) || d[{x[id-1],Y}] > dist+abs(X - x[id-1]))){
					d[{x[id-1],Y}] = dist+abs(X - x[id-1]);
					q.push(make_tuple(dist+abs(X - x[id-1]), x[id-1],Y));
				}
				if(id != r[i] && (!d.count({x[id+1],Y}) || d[{x[id+1],Y}] > dist+abs(X - x[id+1]))){
					d[{x[id+1],Y}] = dist+abs(X - x[id+1]);
					q.push(make_tuple(dist+abs(X - x[id+1]), x[id+1],Y));
				}
			}
		}
		if((!d.count({X, 0}) || d[{X,0}] > dist + Y) && Y <= h[id]){
			d[{X,0}] = dist + Y;
			q.push(make_tuple(dist + Y, X, 0));
		}
		if(y[f] == Y){
			if(id != l[f] && (!d.count({x[id-1],Y}) || d[{x[id-1],Y}] > dist+abs(X - x[id-1]))){
				d[{x[id-1],Y}] = dist+abs(X - x[id-1]);
				q.push(make_tuple(dist+abs(X - x[id-1]), x[id-1],Y));
			}
			if(id != r[f] && (!d.count({x[id+1],Y}) || d[{x[id+1],Y}] > dist+abs(X - x[id+1]))){
				d[{x[id+1],Y}] = dist+abs(X - x[id+1]);
				q.push(make_tuple(dist+abs(X - x[id+1]), x[id+1],Y));
			}
		}
	}
	if(d.count({x[g],0}))return d[{x[g],0}];
	else return -1; 
}

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