Submission #825808

#	Time	Username	Problem	Language	Result	Execution time	Memory
825808		caganyanmaz	Sky Walking (IOI19_walk)	C++17	10 / 100	668 ms	412424 KiB

walk

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

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

constexpr static int MXN = 1e5;
constexpr static int INF = 1e17;
vector<array<int,3>> is[MXN];// Height, prev, next
vector<bool> visited[MXN];
vector<int> min_dist[MXN];


void search_insert(int i, int j, int ch, priority_queue<array<int, 3>>& pq, vector<int32_t>& x)
{
	auto it = lower_bound(is[j].begin(), is[j].end(), array<int, 3>({is[i][ch][0], -1, -1}));
	assert(it != is[j].end() && (*it)[0] == is[i][ch][0]);
	int nh = it - is[j].begin();
	if (min_dist[j][nh] > min_dist[i][ch] + abs(x[j] - x[i]))
	{
		min_dist[j][nh] = min_dist[i][ch] + abs(x[j] - x[i]);
		pq.push({-min_dist[j][nh], j, nh});
	}
}

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)
{
	for (int i = 0; i < l.size(); i++)
	{
		int prev = -1;
		for (int j = l[i]; j <= r[i]; j++)
		{
			if (h[j] >= y[i])
			{
				is[j].pb({y[i], prev, -1});
				if (prev != -1)
					is[prev].back()[2] = j;
				prev = j;
			}
		}
	}
	is[s].pb({0, -1, -1});
	is[g].pb({0, -1, -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;
	pq.push({0, s, 0});
	min_dist[s][0] = 0;
	while (pq.size())
	{
		auto [dist, i, ch] = pq.top();
		pq.pop();
		if (visited[i][ch])
			continue;
		visited[i][ch] = true;
		debug(i, ch, min_dist[i][ch]);
		if (i == 0 && ch == 0)
			debug(is[0][0]);
		if (is[i][ch][1] != -1)
			search_insert(i, is[i][ch][1], ch, pq, x);
		if (is[i][ch][2] != -1)
			search_insert(i, is[i][ch][2], ch, pq, x);
		if (ch > 0 && min_dist[i][ch] + is[i][ch][0] - is[i][ch-1][0] < min_dist[i][ch-1])
		{
			min_dist[i][ch-1] = min_dist[i][ch] + is[i][ch][0] - is[i][ch-1][0];
			pq.push({-min_dist[i][ch-1], i, ch-1});
		}

		if (ch < is[i].size()-1 && min_dist[i][ch] +  is[i][ch+1][0] - is[i][ch-1][0] < min_dist[i][ch+1])
		{
			min_dist[i][ch+1] = min_dist[i][ch] - is[i][ch][0] + is[i][ch+1][0];
			pq.push({-min_dist[i][ch+1], i, ch+1});
		}

		for (int j = ch+1; j < is[i].size(); j++)
		{
			if (min_dist[i][ch] + is[i][j][0] - is[i][ch][0] >= min_dist[i][j])
				break;
			min_dist[i][j] = min_dist[i][ch] - is[i][ch][0] + is[i][j][0];
			pq.push({-min_dist[i][j], i, j});
		}
	}
	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:34: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]
   34 |  for (int i = 0; i < l.size(); i++)
      |                  ~~^~~~~~~~~~
walk.cpp:50: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]
   50 |  for (int i = 0; i < x.size(); i++)
      |                  ~~^~~~~~~~~~
walk.cpp:79:10: 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, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   if (ch < is[i].size()-1 && min_dist[i][ch] +  is[i][ch+1][0] - is[i][ch-1][0] < min_dist[i][ch+1])
      |       ~~~^~~~~~~~~~~~~~~~
walk.cpp:85:24: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::array<long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for (int j = ch+1; j < is[i].size(); j++)
      |                      ~~^~~~~~~~~~~~~~

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