#include "walk.h"
#include <bits/stdc++.h>
using ll = long long;
using std::pair;
using std::vector;
template <class T>
using min_heap = std::priority_queue<T, vector<T>, std::greater<T>>;
ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int src, int dst) {
const int N = (int)X.size();
for (const int pivot : {src, dst}) {
const int M = (int)Y.size();
vector<pair<int, int>> left, right;
for (int i = pivot; i >= 0; --i) {
if (left.empty() or left.back().first < H[i]) {
left.emplace_back(H[i], i);
}
}
for (int i = pivot; i < N; ++i) {
if (right.empty() or right.back().first < H[i]) {
right.emplace_back(H[i], i);
}
}
for (int i = 0; i < M; ++i) {
if (L[i] < pivot and pivot < R[i]) {
const int a = std::lower_bound(left.begin(), left.end(), pair(Y[i], 0))->second;
const int b = std::lower_bound(right.begin(), right.end(), pair(Y[i], 0))->second;
L.push_back(L[i]);
R.push_back(a);
Y.push_back(Y[i]);
L.push_back(b);
R.push_back(R[i]);
Y.push_back(Y[i]);
L[i] = a;
R[i] = b;
}
}
}
vector<vector<pair<int, int>>> graph(N);
const auto add_vertex = [&] {
graph.emplace_back();
return (int)graph.size() - 1;
};
const auto add_edge = [&](const int u, const int v, const int c) {
graph[u].emplace_back(v, c);
graph[v].emplace_back(u, c);
};
vector<vector<pair<int, int>>> vertices(N);
for (int i = 0; i < N; ++i) {
vertices[i].emplace_back(0, i);
}
const int M = (int)Y.size();
vector<int> order(M);
std::iota(order.begin(), order.end(), 0);
std::sort(order.begin(), order.end(), [&](const int i, const int j) {
return Y[i] > Y[j];
});
std::set<int> important;
for (const int e : order) {
if (L[e] == R[e]) {
continue;
}
vertices[L[e]].emplace_back(Y[e], add_vertex());
important.insert(L[e]);
important.insert(R[e]);
auto itr = important.upper_bound(L[e]);
while (true) {
const int a = *std::prev(itr);
const int b = *itr;
const int u = vertices[a].back().second;
vertices[b].emplace_back(Y[e], add_vertex());
const int v = vertices[b].back().second;
add_edge(u, v, X[b] - X[a]);
if (*itr == R[e]) {
break;
} else {
itr = important.erase(itr);
}
}
}
std::set<int> remain;
for (int i = 0; i < N; ++i) {
remain.insert(i);
}
std::reverse(order.begin(), order.end());
for (const int e : order) {
if (L[e] == R[e]) {
continue;
}
vector<int> list;
list.push_back(L[e]);
for (auto itr = remain.upper_bound(L[e]); itr != remain.end() and *itr < R[e]; itr = remain.erase(itr)) {
if (Y[e] <= H[*itr]) {
list.push_back(*itr);
}
}
list.push_back(R[e]);
const int n = (int)list.size();
vector<int> id(n);
for (int i = 0; i < n; ++i) {
id[i] = add_vertex();
vertices[list[i]].emplace_back(Y[e], id[i]);
}
for (int i = 0; i + 1 < n; ++i) {
add_edge(id[i], id[i + 1], X[list[i + 1]] - X[list[i]]);
}
}
for (auto& vec : vertices) {
std::sort(vec.begin(), vec.end());
const int n = (int)vec.size();
for (int i = 0; i + 1 < n; ++i) {
add_edge(vec[i].second, vec[i + 1].second, vec[i + 1].first - vec[i].first);
}
}
vector<ll> dist(graph.size(), std::numeric_limits<ll>::max());
min_heap<pair<ll, int>> heap;
const auto push = [&](const int u, const ll d) {
if (dist[u] > d) {
dist[u] = d;
heap.emplace(d, u);
}
};
push(src, 0);
while (!heap.empty()) {
const auto [d, u] = heap.top();
heap.pop();
if (d > dist[u]) {
continue;
}
for (const auto& [v, c] : graph[u]) {
push(v, d + c);
}
}
const ll ret = dist[dst];
return ret == std::numeric_limits<ll>::max() ? -1 : ret;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 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 |
296 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 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 |
212 KB |
Output is correct |
17 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
580 ms |
58904 KB |
Output is correct |
4 |
Incorrect |
875 ms |
79820 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
208 ms |
23152 KB |
Output is correct |
2 |
Incorrect |
643 ms |
64540 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
208 ms |
23152 KB |
Output is correct |
2 |
Incorrect |
643 ms |
64540 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 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 |
296 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 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 |
212 KB |
Output is correct |
17 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |