oj.uz

Submission #599378

# Submission time Handle Problem Language Result Execution time Memory
599378 2022-07-19T13:16:35 Z FatihSolak Sky Walking (IOI19_walk) C++17
0 / 100
 4000 ms 631112 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: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(auto u:nw){
			hh.insert(u);
		}
	}
	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 Incorrect 0 ms 216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 18580 KB Output is correct
2 Execution timed out 4058 ms 631112 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 18580 KB Output is correct
2 Execution timed out 4058 ms 631112 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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