oj.uz

Submission #950996

# Submission time Handle Problem Language Result Execution time Memory
950996 2024-03-21T03:50:04 Z Trisanu_Das Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 849312 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

int get(int a, int b, int c, int d){
	return abs(c - a) + abs(d - b);
}
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(), m = l.size();
	map<int,vector<pair<int,int> > > adj[n];
	vector<int> st[n], nd[n];
	for(int i = 0; i < m; i++){
		st[l[i]].push_back(y[i]);
		nd[r[i]].push_back(y[i]);
	}
	set<pair<int,int> > hh;
	for(int i = 0; i < n; i++){
		set<pair<int,int> > nw;
		while(hh.size() && hh.begin()->first <= h[i]){
			nw.insert({hh.begin()->first,i});
			adj[i][hh.begin()->first].push_back({hh.begin()->second,hh.begin()->first});
			adj[hh.begin()->second][hh.begin()->first].push_back({i,hh.begin()->first});
			hh.erase(hh.begin());
		}
		for(auto u:nw) hh.insert(u);
		for(auto u:nd[i]) if(hh.lower_bound({u,0}) != hh.end()) hh.erase(hh.lower_bound({u,0}));
		for(auto u:st[i]) hh.insert({u,i});
	}
	for(int i = 0; i < n; i++){
		vector<int> add = {0};
		for(auto u:adj[i]) add.push_back(u.first);
		for(int j = 0; j < add.size() - 1; j++){
			adj[i][add[j]].push_back({i, add[j + 1]});
			adj[i][add[j + 1]].push_back({i, add[j]});
		}
	}
	map<int,long long> dist[n];
	dist[s][0] = 0;
	priority_queue<pair<long long, pair<int,int> > > q;
	q.push({0, {s, 0}});
	while(q.size()){
		auto tp = q.top();
		q.pop();
		tp.first *= -1;
		long long cost = tp.first;
		int a = tp.second.first, b = tp.second.second;
		if(dist[a][b] != cost) continue;
		if(a == g && b == 0) return cost;
		for(auto u:adj[a][b]){
			if(dist[u.first].count(u.second) == 0 || dist[u.first][u.second] > cost + get(x[a], b, x[u.first], u.second)){
				dist[u.first][u.second] = cost + get(x[a], b, x[u.first], u.second);
				q.push({-dist[u.first][u.second], u});
			}
		}
	}
	return -1;
}

Compilation message

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int j = 0; j < add.size() - 1; j++){
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
14.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 443 ms 112440 KB Output is correct
4 Correct 687 ms 188244 KB Output is correct
5 Correct 368 ms 123744 KB Output is correct
6 Correct 337 ms 110932 KB Output is correct
7 Correct 362 ms 124164 KB Output is correct
8 Correct 672 ms 152956 KB Output is correct
9 Correct 429 ms 126492 KB Output is correct
10 Correct 1064 ms 246952 KB Output is correct
11 Correct 294 ms 75100 KB Output is correct
12 Correct 236 ms 81720 KB Output is correct
13 Correct 852 ms 229476 KB Output is correct
14 Correct 166 ms 58448 KB Output is correct
15 Correct 215 ms 79704 KB Output is correct
16 Correct 249 ms 79440 KB Output is correct
17 Correct 200 ms 77136 KB Output is correct
18 Correct 457 ms 67068 KB Output is correct
19 Correct 8 ms 3932 KB Output is correct
20 Correct 91 ms 37908 KB Output is correct
21 Correct 166 ms 72868 KB Output is correct
22 Correct 149 ms 62264 KB Output is correct
23 Correct 403 ms 91396 KB Output is correct
24 Correct 198 ms 77648 KB Output is correct
25 Correct 196 ms 75980 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 19312 KB Output is correct
2 Execution timed out 4062 ms 849312 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 19312 KB Output is correct
2 Execution timed out 4062 ms 849312 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 443 ms 112440 KB Output is correct
21 Correct 687 ms 188244 KB Output is correct
22 Correct 368 ms 123744 KB Output is correct
23 Correct 337 ms 110932 KB Output is correct
24 Correct 362 ms 124164 KB Output is correct
25 Correct 672 ms 152956 KB Output is correct
26 Correct 429 ms 126492 KB Output is correct
27 Correct 1064 ms 246952 KB Output is correct
28 Correct 294 ms 75100 KB Output is correct
29 Correct 236 ms 81720 KB Output is correct
30 Correct 852 ms 229476 KB Output is correct
31 Correct 166 ms 58448 KB Output is correct
32 Correct 215 ms 79704 KB Output is correct
33 Correct 249 ms 79440 KB Output is correct
34 Correct 200 ms 77136 KB Output is correct
35 Correct 457 ms 67068 KB Output is correct
36 Correct 8 ms 3932 KB Output is correct
37 Correct 91 ms 37908 KB Output is correct
38 Correct 166 ms 72868 KB Output is correct
39 Correct 149 ms 62264 KB Output is correct
40 Correct 403 ms 91396 KB Output is correct
41 Correct 198 ms 77648 KB Output is correct
42 Correct 196 ms 75980 KB Output is correct
43 Correct 59 ms 19312 KB Output is correct
44 Execution timed out 4062 ms 849312 KB Time limit exceeded
45 Halted 0 ms 0 KB -