#include "walk.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
int n = x.size();
int m = l.size();
vp pos;
pos.eb(s, 0);
pos.eb(g, 0);
vi ob(n);
iota(all(ob), 0);
sort(all(ob), [&](int i, int j) { return h[i] < h[j]; });
vi oe(m);
iota(all(oe), 0);
sort(all(oe), [&](int i, int j) { return y[i] < y[j]; });
rep(i, m) {
pos.eb(l[i], y[i]);
pos.eb(r[i], y[i]);
}
sort(all(pos));
pos.erase(unique(all(pos)), pos.end());
map<P, int> id;
int sz = pos.size();
rep(i, sz) id[pos[i]] = i;
vvp G(sz);
rep(i, sz - 1) if (pos[i].first == pos[i + 1].first) {
G[i].eb(i + 1, pos[i + 1].second - pos[i].second);
G[i + 1].eb(i, pos[i + 1].second - pos[i].second);
}
rep(i, m) {
int a = id[{l[i], y[i]}];
int b = id[{l[i], y[i]}];
G[a].eb(b, x[r[i]] - x[l[i]]);
G[b].eb(a, x[r[i]] - x[l[i]]);
}
vl dist(sz, linf);
using lp = pair<ll, int>;
priority_queue<lp, vector<lp>, greater<lp>> pq;
dist[id[{s, 0}]] = 0;
pq.emplace(0, id[{s, 0}]);
while (!pq.empty()) {
auto[d, u] = pq.top();
pq.pop();
if (dist[u] < d) continue;
cerr << d << ' ' << pos[u].first << ' ' << pos[u].second << endl;
for (auto[v, len] : G[u]) {
if (chmin(dist[v], d + len)) pq.emplace(d + len, v);
}
}
ll ans = dist[id[{g, 0}]];
return (ans == linf ? -1 : ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
9884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
9884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
