oj.uz

Submission #430633

# Submission time Handle Problem Language Result Execution time Memory
430633 2021-06-16T17:41:01 Z Hazem Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 349344 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++){
		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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 272 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 9 ms 580 KB Output is correct
6 Correct 6 ms 552 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 5 ms 460 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 15 ms 716 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 12 ms 728 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Execution timed out 4094 ms 273424 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1366 ms 36196 KB Output is correct
2 Execution timed out 4101 ms 349344 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1366 ms 36196 KB Output is correct
2 Execution timed out 4101 ms 349344 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 272 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 9 ms 580 KB Output is correct
6 Correct 6 ms 552 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 5 ms 460 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 15 ms 716 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 12 ms 728 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Execution timed out 4094 ms 273424 KB Time limit exceeded
21 Halted 0 ms 0 KB -