Submission #599379

#	Time	Username	Problem	Language	Result	Execution time	Memory
599379		FatihSolak	Sky Walking (IOI19_walk)	C++17	24 / 100	4107 ms	819408 KiB

walk

#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 (stderr)

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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43