oj.uz

Submission #430623

# Submission time Handle Problem Language Result Execution time Memory
430623 2021-06-16T17:25:48 Z Hazem Sky Walking (IOI19_walk) C++14
0 / 100
 4000 ms 344132 KB 
#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++)
		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({x[j-1],y[i]});
					adj[{x[j-1],y[i]}].push_back({x[j],y[i]});
				}
				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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1329 ms 37016 KB Output is correct
2 Execution timed out 4091 ms 344132 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1329 ms 37016 KB Output is correct
2 Execution timed out 4091 ms 344132 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -