oj.uz

Submission #1058297

# Submission time Handle Problem Language Result Execution time Memory
1058297 2024-08-14T09:15:40 Z Unforgettablepl Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 1048576 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

long long min_distance(vector<int> x,vector<int> h,vector<int> l,
					   vector<int> r,vector<int> y,int s,int g){
	int n = x.size();
	int m = l.size();
	vector<vector<pair<int,int>>> points(n);
	vector<vector<pair<int,int>>> adj(n);
	int S = n;
	for(int i=0;i<n;i++)points[i].emplace_back(i,0);
	vector<tuple<int,int,int>> skywalks;
	for(int i=0;i<m;i++)skywalks.emplace_back(y[i],l[i],r[i]);
	sort(skywalks.begin(), skywalks.end());
	auto add_point = [&](int x,int h) {
		adj.emplace_back();
		adj[S].emplace_back(points[x].back().first,h-points[x].back().second);
		adj[points[x].back().first].emplace_back(S,h-points[x].back().second);
		points[x].emplace_back(S,h);
		return S++;
	};
	for(int i=0;i<m;i++){
		auto [height,left,right] = skywalks[i];
		auto last_point = add_point(left,height);
		auto last_x = x[left];
		for(int j=left+1;j<=right;j++) {
			if(h[j]<height)continue;
			auto curr_point = add_point(j,height);
			adj[curr_point].emplace_back(last_point,x[j]-last_x);
			adj[last_point].emplace_back(curr_point,x[j]-last_x);
			last_point=curr_point;
			last_x=x[j];
		}
	}
	priority_queue<pair<long long,int>> q;
	vector<bool> visited(S);
	q.emplace(0,s);
	while(!q.empty()) {
		auto [dist,idx] = q.top();q.pop();dist=-dist;
		if(visited[idx])continue;
		visited[idx]=true;
		if(idx==g)return dist;
		for(auto&[v,c]:adj[idx])if(!visited[v])q.emplace(-dist-c,v);
	}
	return -1;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 440 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 135 ms 75420 KB Output is correct
4 Correct 331 ms 97096 KB Output is correct
5 Correct 171 ms 68272 KB Output is correct
6 Correct 595 ms 62120 KB Output is correct
7 Correct 161 ms 69036 KB Output is correct
8 Correct 190 ms 82876 KB Output is correct
9 Correct 232 ms 79228 KB Output is correct
10 Correct 404 ms 103024 KB Output is correct
11 Correct 118 ms 42316 KB Output is correct
12 Correct 127 ms 36384 KB Output is correct
13 Correct 427 ms 98196 KB Output is correct
14 Correct 2477 ms 33844 KB Output is correct
15 Correct 1194 ms 37968 KB Output is correct
16 Correct 120 ms 36012 KB Output is correct
17 Correct 122 ms 34296 KB Output is correct
18 Execution timed out 4097 ms 23400 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 13580 KB Output is correct
2 Correct 1090 ms 431924 KB Output is correct
3 Runtime error 1078 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 13580 KB Output is correct
2 Correct 1090 ms 431924 KB Output is correct
3 Runtime error 1078 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 440 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 135 ms 75420 KB Output is correct
21 Correct 331 ms 97096 KB Output is correct
22 Correct 171 ms 68272 KB Output is correct
23 Correct 595 ms 62120 KB Output is correct
24 Correct 161 ms 69036 KB Output is correct
25 Correct 190 ms 82876 KB Output is correct
26 Correct 232 ms 79228 KB Output is correct
27 Correct 404 ms 103024 KB Output is correct
28 Correct 118 ms 42316 KB Output is correct
29 Correct 127 ms 36384 KB Output is correct
30 Correct 427 ms 98196 KB Output is correct
31 Correct 2477 ms 33844 KB Output is correct
32 Correct 1194 ms 37968 KB Output is correct
33 Correct 120 ms 36012 KB Output is correct
34 Correct 122 ms 34296 KB Output is correct
35 Execution timed out 4097 ms 23400 KB Time limit exceeded
36 Halted 0 ms 0 KB -