oj.uz

Submission #825792

# Submission time Handle Problem Language Result Execution time Memory
825792 2023-08-15T08:07:46 Z tomruk Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 612444 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
map<int,vector<int>> adj[N];
map<int,long long> d[N];
long long min_distance(vector<int> p, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	int n = p.size();
	int m = l.size();
	vector<pair<int,int>> v;
	for(int i = 0;i<n;i++){
		v.push_back({h[i],i});
		adj[i][0].push_back(i);
	}
	for(int i = 0;i<m;i++){
		v.push_back({y[i],~i});
	}
	sort(v.rbegin(),v.rend());
	set<int> active;
	for(auto u:v){
		if(u.second < 0){
			u.second = ~u.second;
			auto it = active.lower_bound(l[u.second]);
			while(1){
				auto it2 = it;
				it2++;
				if(it2 == active.end() || *it2 > r[u.second])
					break;
				adj[*it][y[u.second]].push_back(*it2);
				adj[*it2][y[u.second]].push_back(*it);
				it = it2;
			}
		}
		else{
			active.insert(u.second);
		}
	}
	priority_queue<pair<long long,pair<int,int>>> q;
	d[s][0] = 0;
	q.push({-d[s][0],{s,0}});
	while(q.size()){
		auto tp = q.top();
		q.pop();
		tp.first *= -1;
		int x = tp.second.first;
		int y = tp.second.second;
		if(tp.first != d[x][y])
			continue;
		// cout << x << ' ' << y << endl;
		// cout << tp.first << endl;
		for(auto u:adj[x][y]){
			long long nw = abs(p[x] - p[u]) + tp.first;
			if(d[u].count(y) == 0 || d[u][y] > nw){
				d[u][y] = nw;
				q.push({-d[u][y],{u,y}});
			}
		}
		auto it = adj[x].find(y);
		if(next(it) != adj[x].end()){
			long long nw = abs(y - next(it)->first) + tp.first;
			if(d[x].count(next(it)->first) == 0 || d[x][next(it)->first] > nw){
				d[x][next(it)->first] = nw;
				q.push({-d[x][next(it)->first],{x,next(it)->first}});
			}
		}
		if(it != adj[x].begin()){
			long long nw = abs(y - prev(it)->first) + tp.first;
			if(d[x].count(prev(it)->first) == 0 || d[x][prev(it)->first] > nw){
				d[x][prev(it)->first] = nw;
				q.push({-d[x][prev(it)->first],{x,prev(it)->first}});
			}
		}
	}
	return (d[g].count(0)?d[g][0]:-1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9640 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 4 ms 9696 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 4 ms 9700 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Correct 5 ms 9812 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 1213 ms 135844 KB Output is correct
4 Correct 745 ms 161700 KB Output is correct
5 Correct 350 ms 99516 KB Output is correct
6 Correct 308 ms 90904 KB Output is correct
7 Correct 345 ms 99540 KB Output is correct
8 Correct 1773 ms 172340 KB Output is correct
9 Correct 515 ms 104088 KB Output is correct
10 Correct 1157 ms 213364 KB Output is correct
11 Correct 424 ms 85564 KB Output is correct
12 Correct 265 ms 75424 KB Output is correct
13 Correct 897 ms 190292 KB Output is correct
14 Correct 169 ms 55024 KB Output is correct
15 Correct 246 ms 74812 KB Output is correct
16 Correct 235 ms 74044 KB Output is correct
17 Correct 241 ms 71868 KB Output is correct
18 Correct 348 ms 69308 KB Output is correct
19 Correct 11 ms 12776 KB Output is correct
20 Correct 83 ms 41200 KB Output is correct
21 Correct 213 ms 68212 KB Output is correct
22 Correct 258 ms 74596 KB Output is correct
23 Correct 300 ms 84196 KB Output is correct
24 Correct 231 ms 73512 KB Output is correct
25 Correct 222 ms 71100 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 23956 KB Output is correct
2 Execution timed out 4121 ms 612444 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 23956 KB Output is correct
2 Execution timed out 4121 ms 612444 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9640 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 4 ms 9696 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 4 ms 9700 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Correct 5 ms 9812 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 1213 ms 135844 KB Output is correct
21 Correct 745 ms 161700 KB Output is correct
22 Correct 350 ms 99516 KB Output is correct
23 Correct 308 ms 90904 KB Output is correct
24 Correct 345 ms 99540 KB Output is correct
25 Correct 1773 ms 172340 KB Output is correct
26 Correct 515 ms 104088 KB Output is correct
27 Correct 1157 ms 213364 KB Output is correct
28 Correct 424 ms 85564 KB Output is correct
29 Correct 265 ms 75424 KB Output is correct
30 Correct 897 ms 190292 KB Output is correct
31 Correct 169 ms 55024 KB Output is correct
32 Correct 246 ms 74812 KB Output is correct
33 Correct 235 ms 74044 KB Output is correct
34 Correct 241 ms 71868 KB Output is correct
35 Correct 348 ms 69308 KB Output is correct
36 Correct 11 ms 12776 KB Output is correct
37 Correct 83 ms 41200 KB Output is correct
38 Correct 213 ms 68212 KB Output is correct
39 Correct 258 ms 74596 KB Output is correct
40 Correct 300 ms 84196 KB Output is correct
41 Correct 231 ms 73512 KB Output is correct
42 Correct 222 ms 71100 KB Output is correct
43 Correct 58 ms 23956 KB Output is correct
44 Execution timed out 4121 ms 612444 KB Time limit exceeded
45 Halted 0 ms 0 KB -