This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "walk.h"
namespace my {
const int N = 1e6 + 10;
map<pair<int, int>, int> was;
int id(int x, int y) {
auto p = mp(x, y);
if (was.count(p)) {
return was[p];
} else {
int v = (int)was.size();
assert(v < N);
return was[p] = v;
}
}
vector<pair<int, int>> g[N];
set<int> ys[N];
void edge(int v, int u, int w) {
g[v].emplace_back(u, w);
g[u].emplace_back(v, w);
}
using T = pair<ll, int>;
const ll INF = 1e18;
priority_queue<T, vector<T>, greater<T>> q;
ll dst[N];
}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int st, int fi) {
using namespace my;
for (int i = 0; i < (int)y.size(); ++i) {
int lst = l[i];
for (int j = l[i] + 1; j <= r[i]; ++j) {
if (h[j] < y[i]) {
continue;
}
edge(id(x[lst], y[i]), id(x[j], y[i]), abs(x[lst] - x[j]));
lst = j;
}
for (int j = l[i]; j <= r[i]; ++j) {
if (h[j] >= y[i]) {
ys[j].insert(y[i]);
}
}
}
for (int i = 0; i < (int)x.size(); ++i) {
int ly = 0, lv = id(x[i], 0);
for (int cur : ys[i]) {
int ver = id(x[i], cur);
edge(lv, ver, abs(cur - ly));
ly = cur, lv = ver;
}
}
int from = id(x[st], 0), to = id(x[fi], 0);
fill_n(dst, N, INF);
dst[from] = 0;
q.emplace(dst[from], from);
while (q.size()) {
ll d, w;
int v, u;
tie(d, v) = q.top(); q.pop();
if (d != dst[v]) {
continue;
}
for (auto e : g[v]) {
u = e.x, w = e.y;
if (dst[u] > dst[v] + w) {
dst[u] = dst[v] + w;
q.emplace(dst[u], u);
}
}
}
return dst[to];
}
#ifdef LC
#include "grader.cpp"
#endif
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |