Submission #826090

#	Time	Username	Problem	Language	Result	Execution time	Memory
826090		caganyanmaz	Sky Walking (IOI19_walk)	C++14	0 / 100	66 ms	18596 KiB

walk

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define int int64_t

#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int MXN = 1e5 + 5;
constexpr static int INF = 1e17;
vector<array<int,2>> is[MXN];// Height, type
vector<bool> visited[MXN];
vector<int> min_dist[MXN];



long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t s, int32_t g)
{
	int n = x.size();
	int m = y.size();
	for (int i = 0; i < m; i++)
	{
		is[l[i]].pb({y[i], r[i]});
		is[r[i]].pb({y[i], l[i]});
	}
	is[s].pb({0, -1});
	is[g].pb({0, -1});
	for (int i = 0; i < x.size(); i++)
	{
		sort(is[i].begin(), is[i].end());
		min_dist[i] = vector<int> (is[i].size(), INF);
		visited[i] = vector<bool>(is[i].size(), false);
	}
	priority_queue<array<int, 3>> pq; // dist, tower, index
	min_dist[s][0] = 0;
	pq.push({0, s, 0});
	int res = 0;
	while (pq.size())
	{
		auto [dist, i, j] = pq.top();
		pq.pop();
		if (visited[i][j])
			continue;
		if (i == g && j == 0)
			break;
		visited[i][j] = true;
		int ni = is[i][j][1];
		if (ni != -1)
		{
			int nj = lower_bound(is[ni].begin(), is[ni].end(), array<int, 2>({is[i][j][0], i})) - is[ni].begin();
			if (min_dist[ni][nj] > min_dist[i][j] + abs(x[ni] - x[i]))
			{
				min_dist[ni][nj] = min_dist[i][j] +  abs(x[ni] - x[i]);
				pq.push({-min_dist[ni][nj], ni, nj});
			}
		}
		if (j > 0 && min_dist[i][j-1] > min_dist[i][j] + abs(is[i][j][0] - is[i][j-1][0]))
		{
			min_dist[i][j-1] = min_dist[i][j] + abs(is[i][j][0] - is[i][j-1][0]);
			pq.push({-min_dist[i][j-1], i, j-1});
		}
		if (j < is[i].size()-1 && min_dist[i][j+1] > min_dist[i][j] + abs(is[i][j][0] - is[i][j+1][0]))
		{
			min_dist[i][j+1] = min_dist[i][j] + abs(is[i][j][0] - is[i][j+1][0]);
			pq.push({-min_dist[i][j+1], i, j+1});
		}
	}
	if (min_dist[g][0] >= INF)
		return -1;
	return min_dist[g][0];
}

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>, int32_t, int32_t)':
walk.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (int i = 0; i < x.size(); i++)
      |                  ~~^~~~~~~~~~
walk.cpp:43:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |   auto [dist, i, j] = pq.top();
      |        ^
walk.cpp:65:9: warning: comparison of integer expressions of different signedness: 'std::tuple_element<2, std::array<long int, 3> >::type' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   if (j < is[i].size()-1 && min_dist[i][j+1] > min_dist[i][j] + abs(is[i][j][0] - is[i][j+1][0]))
      |       ~~^~~~~~~~~~~~~~~~
walk.cpp:22:6: warning: unused variable 'n' [-Wunused-variable]
   22 |  int n = x.size();
      |      ^
walk.cpp:40:6: warning: unused variable 'res' [-Wunused-variable]
   40 |  int res = 0;
      |      ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43