#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
ll ST12(vt<int> X, vt<int> H, vt<int> L, vt<int> R, vt<int> Y, int S, int G, int LEN) {
const int N = size(X), M = size(L);
vt<ari3> points;
FOR(i, 0, M-1)
FOR(j, L[i], R[i])
points.push_back({j, Y[i], i});
FOR(i, 0, N-1)
points.push_back({i, 0, -1});
sort(all(points));
points.erase(unique(all(points)), end(points));
int prv[M];
memset(prv, -1, sizeof(prv));
vt<ari2> adj[size(points)];
priority_queue<arl2, vt<arl2>, greater<arl2>> pq;
ll dst[size(points)];
memset(dst, 0x3f, sizeof(dst));
FOR(i, 0, size(points)-1) {
if (i && points[i][0] == points[i-1][0] && points[i][1] <= H[points[i][0]]) {
adj[i-1].push_back({i, points[i][1] - points[i-1][1]});
adj[i].push_back({i-1, points[i][1] - points[i-1][1]});
}
if (~points[i][2] && ~prv[points[i][2]]) {
adj[i].push_back({prv[points[i][2]], X[points[i][0]] - X[points[prv[points[i][2]]][0]]});
adj[prv[points[i][2]]].push_back({i, X[points[i][0]] - X[points[prv[points[i][2]]][0]]});
}
if (~points[i][2])
prv[points[i][2]] = i;
if (points[i][0] == S && !points[i][1])
pq.push({dst[i] = 0, i});
}
while (size(pq)) {
auto [d, i] = pq.top();
pq.pop();
if (points[i][0] == G && !points[i][1])
return d;
if (d > dst[i])
continue;
#ifdef DEBUG
cout << "at " << X[points[i][0]] << ' ' << points[i][1] << " with dist of " << d << '\n';
#endif
for (auto &[j, v] : adj[i])
if (d + v < dst[j])
pq.push({dst[j] = d + v, j});
}
return -1;
}
ll min_distance(vt<int> X, vt<int> H, vt<int> L, vt<int> R, vt<int> Y, int S, int G) {
const int N = size(X), M = size(L);
bool sub2 = true;
int LEN = N;
FOR(i, 0, M-1) {
sub2 &= R[i] - L[i] < 15;
LEN += R[i] - L[i] + 1;
}
if (sub2 || N < 51 && M < 51)
return ST12(X, H, L, R, Y, S, G, LEN);
}
Compilation message
walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:78:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
78 | if (sub2 || N < 51 && M < 51)
| ~~~~~~~^~~~~~~~~
walk.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
80 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
242 ms |
76080 KB |
Output is correct |
4 |
Correct |
375 ms |
83896 KB |
Output is correct |
5 |
Runtime error |
3386 ms |
1048576 KB |
Execution killed with signal 9 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
13516 KB |
Output is correct |
2 |
Correct |
1901 ms |
467244 KB |
Output is correct |
3 |
Execution timed out |
4057 ms |
795528 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
13516 KB |
Output is correct |
2 |
Correct |
1901 ms |
467244 KB |
Output is correct |
3 |
Execution timed out |
4057 ms |
795528 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
242 ms |
76080 KB |
Output is correct |
21 |
Correct |
375 ms |
83896 KB |
Output is correct |
22 |
Runtime error |
3386 ms |
1048576 KB |
Execution killed with signal 9 |
23 |
Halted |
0 ms |
0 KB |
- |