Submission #950996

#	Time	Username	Problem	Language	Result	Execution time	Memory
950996		Trisanu_Das	Sky Walking (IOI19_walk)	C++17	24 / 100	4062 ms	849312 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(), 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 (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: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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43