oj.uz

Submission #826106

# Submission time Handle Problem Language Result Execution time Memory
826106 2023-08-15T10:28:26 Z caganyanmaz Sky Walking (IOI19_walk) C++17
10 / 100
 819 ms 569456 KB 
#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 = 1e6;
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)
{
	int nh = lower_bound(is[j].begin(), is[j].end(), array<int, 3>({is[i][ch][0], -1, -1})) - 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] + abs(is[i][ch][0] - is[i][ch-1][0]) < min_dist[i][ch-1])
		{
			min_dist[i][ch-1] = min_dist[i][ch] + abs(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] + abs(is[i][ch][0] - is[i][ch+1][0]);
			pq.push({-min_dist[i][ch+1], i, ch+1});
		}

	}
	if (min_dist[g][0] >= INF)
		return -1;
	return min_dist[g][0];
}

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>, int32_t, int32_t)':
walk.cpp:32: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]
   32 |  for (int i = 0; i < l.size(); i++)
      |                  ~~^~~~~~~~~~
walk.cpp:48: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]
   48 |  for (int i = 0; i < x.size(); i++)
      |                  ~~^~~~~~~~~~
walk.cpp:77: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]
   77 |   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])
      |       ~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 86336 KB Output is correct
2 Correct 41 ms 86320 KB Output is correct
3 Correct 39 ms 86376 KB Output is correct
4 Correct 46 ms 86384 KB Output is correct
5 Correct 43 ms 86356 KB Output is correct
6 Correct 35 ms 86400 KB Output is correct
7 Correct 44 ms 86412 KB Output is correct
8 Correct 37 ms 86392 KB Output is correct
9 Correct 44 ms 86356 KB Output is correct
10 Correct 44 ms 86376 KB Output is correct
11 Correct 46 ms 86360 KB Output is correct
12 Correct 45 ms 86408 KB Output is correct
13 Correct 47 ms 86356 KB Output is correct
14 Correct 42 ms 86312 KB Output is correct
15 Correct 36 ms 86300 KB Output is correct
16 Correct 40 ms 86376 KB Output is correct
17 Correct 47 ms 86352 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 86380 KB Output is correct
2 Correct 40 ms 86344 KB Output is correct
3 Correct 329 ms 120504 KB Output is correct
4 Incorrect 358 ms 122760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 92808 KB Output is correct
2 Runtime error 819 ms 569456 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 92808 KB Output is correct
2 Runtime error 819 ms 569456 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 86336 KB Output is correct
2 Correct 41 ms 86320 KB Output is correct
3 Correct 39 ms 86376 KB Output is correct
4 Correct 46 ms 86384 KB Output is correct
5 Correct 43 ms 86356 KB Output is correct
6 Correct 35 ms 86400 KB Output is correct
7 Correct 44 ms 86412 KB Output is correct
8 Correct 37 ms 86392 KB Output is correct
9 Correct 44 ms 86356 KB Output is correct
10 Correct 44 ms 86376 KB Output is correct
11 Correct 46 ms 86360 KB Output is correct
12 Correct 45 ms 86408 KB Output is correct
13 Correct 47 ms 86356 KB Output is correct
14 Correct 42 ms 86312 KB Output is correct
15 Correct 36 ms 86300 KB Output is correct
16 Correct 40 ms 86376 KB Output is correct
17 Correct 47 ms 86352 KB Output is correct
18 Correct 46 ms 86380 KB Output is correct
19 Correct 40 ms 86344 KB Output is correct
20 Correct 329 ms 120504 KB Output is correct
21 Incorrect 358 ms 122760 KB Output isn't correct
22 Halted 0 ms 0 KB -