#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
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;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
14336 KB |
Output is correct |
| 2 |
Incorrect |
66 ms |
18596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
14336 KB |
Output is correct |
| 2 |
Incorrect |
66 ms |
18596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
