oj.uz

Submission #599376

# Submission time Handle Problem Language Result Execution time Memory
599376 2022-07-19T13:14:43 Z FatihSolak Sky Walking (IOI19_walk) C++17
0 / 100
 1163 ms 242808 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:st[i]){
			hh.insert({u,i});
		}
		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(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:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int j = 0;j<add.size()-1;j++){
      |                 ~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 531 ms 112052 KB Output is correct
4 Correct 778 ms 184212 KB Output is correct
5 Correct 435 ms 120056 KB Output is correct
6 Correct 383 ms 107496 KB Output is correct
7 Correct 430 ms 120492 KB Output is correct
8 Correct 804 ms 150952 KB Output is correct
9 Correct 499 ms 122752 KB Output is correct
10 Correct 1163 ms 242808 KB Output is correct
11 Correct 336 ms 72200 KB Output is correct
12 Correct 206 ms 77768 KB Output is correct
13 Correct 993 ms 225328 KB Output is correct
14 Correct 212 ms 54756 KB Output is correct
15 Incorrect 235 ms 67004 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 3924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 3924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -