Submission #430633

#	Time	Username	Problem	Language	Result	Execution time	Memory
430633		Hazem	Sky Walking (IOI19_walk)	C++14	10 / 100	4101 ms	349344 KiB

walk

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

#define LL long long
#define F first
#define S second

using namespace std;

priority_queue<pair<LL,pair<int,int>>>que;
map<int,vector<int>>mp;
map<pair<int,int>,vector<pair<int,int>>>adj;
map<pair<int,int>,LL>vis,dis;

void dijikstra(int stx,int sty){

	que.push({0,{stx,sty}});

	while(!que.empty()){
		
		LL x1 = que.top().S.F,y1 = que.top().S.S;
		que.pop();

		if(vis[{x1,y1}])
			continue;
		
		vis[{x1,y1}] = 1;
		for(auto x:adj[{x1,y1}]){
			LL x2 = x.F,y2 = x.S;
			if(!dis[{x2,y2}]||dis[{x2,y2}]>dis[{x1,y1}]+abs(x1-x2)+abs(y1-y2))
				dis[{x2,y2}] = dis[{x1,y1}]+abs(x1-x2)+abs(y1-y2);
			que.push({-dis[{x2,y2}],{x2,y2}});
		}
	}
}

long long min_distance(vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	
	int n = x.size();int m = l.size();

	for(int i=0;i<n;i++){
		
		mp[x[i]].push_back(0);
		mp[x[i]].push_back(h[i]);

		pair<int,int>p = make_pair(x[i],0);
		adj[p].push_back({x[i],h[i]});
		adj[{x[i],h[i]}].push_back({x[i],0});
	}

	for(int i=0;i<m;i++){
		int last = 0;
		for(int j=l[i];j<=r[i];j++){
			if(h[j]>=y[i]){
				if(j>l[i]){
					adj[{x[j],y[i]}].push_back({last,y[i]});
					adj[{last,y[i]}].push_back({x[j],y[i]});
				}
				last = x[j];
				mp[x[j]].push_back(y[i]);
				for(auto x10:mp[x[j]]){
					adj[{x[j],y[i]}].push_back({x[j],x10});
					adj[{x[j],x10}].push_back({x[j],y[i]});
				}
			}
		}
	}

	dijikstra(x[s],0);
	if(!dis[{x[g],0}])
		return -1;
	return dis[{x[g],0}];
}

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