#pragma GCC optimize("O3")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx2")
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define sint signed
#define int long long
#define pii pair<int, int>
int min_distance(std::vector<sint> x, std::vector<sint> h, std::vector<sint> l, std::vector<sint> r, std::vector<sint> y, sint ss, sint gg) {
int n = x.size(), m = l.size();
vector<vector<pii>> g;
vector<vector<pii>> c(n);
int t = 0;
for (int j = 0; j < m; j++) {
int last = -1, lp;
for (int i = l[j]; i <= r[j]; i++) {
if (h[i] < y[j])
continue;
c[i].push_back({y[j], t++});
g.push_back(vector<pii>());
if (last != -1) {
g[lp].push_back({t - 1, x[i] - x[last]});
g[t - 1].push_back({lp, x[i] - x[last]});
}
last = i, lp = t - 1;
}
}
int s = 0, f = 0;
g.push_back(vector<pii>());
g.push_back(vector<pii>());
for (int i = 0; i < n; i++) {
if (i == ss) {
s = t;
c[i].push_back({0, t++});
}
if (i == gg) {
f = t;
c[i].push_back({0, t++});
}
sort(c[i].begin(), c[i].end());
for (int j = 0; j < (int)c[i].size() - 1; j++) {
int v = c[i][j].second, u = c[i][j + 1].second;
int d = c[i][j + 1].first - c[i][j].first;
g[v].push_back({u, d});
g[u].push_back({v, d});
}
}
//for (int i = 0; i < t; i++) {
// cout << i << " : " ;
// for (pii j : g[i])
// cout << "{ " << j.first << ' ' << j.second << " } ";
// cout << '\n';
//}
int a = 0;
priority_queue<pii, vector<pii>, greater<pii>> q;
const int inf = 2e18;
vector<int> d(t, inf);
q.push({0, s});
while (q.size()) {
int v = q.top().second, dst = q.top().first;
q.pop();
if (d[v] != inf)
continue;
d[v] = dst;
for (auto u : g[v]) {
if (d[u.first] == inf) {
q.push({dst + u.second, u.first});
}
}
}
if (d[f] == inf)
return -1;
else
return d[f];
}
Compilation message
walk.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization("unroll-loops")
|
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:61:9: warning: unused variable 'a' [-Wunused-variable]
61 | int a = 0;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
296 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
732 ms |
102216 KB |
Output is correct |
4 |
Correct |
687 ms |
106416 KB |
Output is correct |
5 |
Correct |
480 ms |
91848 KB |
Output is correct |
6 |
Correct |
947 ms |
80892 KB |
Output is correct |
7 |
Correct |
472 ms |
91868 KB |
Output is correct |
8 |
Correct |
937 ms |
128580 KB |
Output is correct |
9 |
Correct |
520 ms |
91956 KB |
Output is correct |
10 |
Correct |
917 ms |
147976 KB |
Output is correct |
11 |
Correct |
349 ms |
54920 KB |
Output is correct |
12 |
Correct |
197 ms |
32340 KB |
Output is correct |
13 |
Correct |
821 ms |
131784 KB |
Output is correct |
14 |
Correct |
2859 ms |
32024 KB |
Output is correct |
15 |
Correct |
1565 ms |
31860 KB |
Output is correct |
16 |
Correct |
245 ms |
33788 KB |
Output is correct |
17 |
Correct |
309 ms |
32672 KB |
Output is correct |
18 |
Execution timed out |
4050 ms |
15300 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
17428 KB |
Output is correct |
2 |
Execution timed out |
4091 ms |
699080 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
17428 KB |
Output is correct |
2 |
Execution timed out |
4091 ms |
699080 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
296 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
732 ms |
102216 KB |
Output is correct |
21 |
Correct |
687 ms |
106416 KB |
Output is correct |
22 |
Correct |
480 ms |
91848 KB |
Output is correct |
23 |
Correct |
947 ms |
80892 KB |
Output is correct |
24 |
Correct |
472 ms |
91868 KB |
Output is correct |
25 |
Correct |
937 ms |
128580 KB |
Output is correct |
26 |
Correct |
520 ms |
91956 KB |
Output is correct |
27 |
Correct |
917 ms |
147976 KB |
Output is correct |
28 |
Correct |
349 ms |
54920 KB |
Output is correct |
29 |
Correct |
197 ms |
32340 KB |
Output is correct |
30 |
Correct |
821 ms |
131784 KB |
Output is correct |
31 |
Correct |
2859 ms |
32024 KB |
Output is correct |
32 |
Correct |
1565 ms |
31860 KB |
Output is correct |
33 |
Correct |
245 ms |
33788 KB |
Output is correct |
34 |
Correct |
309 ms |
32672 KB |
Output is correct |
35 |
Execution timed out |
4050 ms |
15300 KB |
Time limit exceeded |
36 |
Halted |
0 ms |
0 KB |
- |