oj.uz

답안 #361135

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361135 2021-01-28T11:29:17 Z tengiz05 Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 4644 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 4 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 5 ms 364 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Execution timed out 4090 ms 4644 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4094 ms 3308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4094 ms 3308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 4 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 5 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 0 ms 364 KB Output is correct
20 Execution timed out 4090 ms 4644 KB Time limit exceeded
21 Halted 0 ms 0 KB -