oj.uz

Submission #599379

# Submission time Handle Problem Language Result Execution time Memory
599379 2022-07-19T13:17:05 Z FatihSolak Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 819408 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();
	int m = l.size();
	map<int,vector<pair<int,int>>> adj[n];
	vector<int> st[n];
	vector<int> 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;
		int b = tp.second.second;
		//cout << a << " " << b << " " << cost << endl;
		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:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 216 KB Output is correct
10 Correct 1 ms 424 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 2 ms 468 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 537 ms 113092 KB Output is correct
4 Correct 793 ms 185292 KB Output is correct
5 Correct 528 ms 121136 KB Output is correct
6 Correct 395 ms 108452 KB Output is correct
7 Correct 496 ms 121540 KB Output is correct
8 Correct 828 ms 151884 KB Output is correct
9 Correct 520 ms 123672 KB Output is correct
10 Correct 1213 ms 243676 KB Output is correct
11 Correct 372 ms 73008 KB Output is correct
12 Correct 229 ms 78744 KB Output is correct
13 Correct 992 ms 226256 KB Output is correct
14 Correct 202 ms 55756 KB Output is correct
15 Correct 315 ms 77456 KB Output is correct
16 Correct 255 ms 79536 KB Output is correct
17 Correct 246 ms 76944 KB Output is correct
18 Correct 566 ms 67028 KB Output is correct
19 Correct 9 ms 3924 KB Output is correct
20 Correct 110 ms 37832 KB Output is correct
21 Correct 198 ms 72712 KB Output is correct
22 Correct 172 ms 62256 KB Output is correct
23 Correct 453 ms 91332 KB Output is correct
24 Correct 252 ms 77516 KB Output is correct
25 Correct 253 ms 76068 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 19152 KB Output is correct
2 Execution timed out 4107 ms 819408 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 19152 KB Output is correct
2 Execution timed out 4107 ms 819408 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 216 KB Output is correct
10 Correct 1 ms 424 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 296 KB Output is correct
19 Correct 1 ms 300 KB Output is correct
20 Correct 537 ms 113092 KB Output is correct
21 Correct 793 ms 185292 KB Output is correct
22 Correct 528 ms 121136 KB Output is correct
23 Correct 395 ms 108452 KB Output is correct
24 Correct 496 ms 121540 KB Output is correct
25 Correct 828 ms 151884 KB Output is correct
26 Correct 520 ms 123672 KB Output is correct
27 Correct 1213 ms 243676 KB Output is correct
28 Correct 372 ms 73008 KB Output is correct
29 Correct 229 ms 78744 KB Output is correct
30 Correct 992 ms 226256 KB Output is correct
31 Correct 202 ms 55756 KB Output is correct
32 Correct 315 ms 77456 KB Output is correct
33 Correct 255 ms 79536 KB Output is correct
34 Correct 246 ms 76944 KB Output is correct
35 Correct 566 ms 67028 KB Output is correct
36 Correct 9 ms 3924 KB Output is correct
37 Correct 110 ms 37832 KB Output is correct
38 Correct 198 ms 72712 KB Output is correct
39 Correct 172 ms 62256 KB Output is correct
40 Correct 453 ms 91332 KB Output is correct
41 Correct 252 ms 77516 KB Output is correct
42 Correct 253 ms 76068 KB Output is correct
43 Correct 69 ms 19152 KB Output is correct
44 Execution timed out 4107 ms 819408 KB Time limit exceeded
45 Halted 0 ms 0 KB -