#include "walk.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
struct SegTree {
int n, N;
vi tree;
int def = LLONG_MAX / 2;
SegTree(vi values) {
n = values.size();
N = 1;
while (N < n) N *= 2;
tree = vi(2 * N, def);
loop(i, n) {
tree[N + i] = values[i];
}
for (int i = N - 1; i >= 1; i--) {
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
}
int merge(int a, int b) {
return min(a, b);
}
void set(int idx, int v) {
idx += N;
tree[idx] = v;
idx /= 2;
while (idx) {
tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
idx /= 2;
}
}
int get(int l, int r, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1) {
tr = N;
}
if (tr <= l || tl >= r) {
return def;
}
if (tl >= l && tr <= r) {
return tree[i];
}
int tm = (tl + tr) / 2;
return merge(get(l, r, i * 2, tl, tm), get(l, r, i * 2 + 1, tm, tr));
}
};
long long min_distance(std::vector<signed> xs, std::vector<signed> hs, std::vector<signed> ls, std::vector<signed> rs, std::vector<signed> ys, signed s, signed g) {
int n = xs.size();
int m = ls.size();
vector<tuple<int, int, int>> bridges(m);
loop(i, m) {
bridges[i] = { ys[i], ls[i], rs[i] };
}
sort(all(bridges));
sort(all(ys));
vii buildings(n);
loop(i, n) {
buildings[i] = { xs[i], hs[i] };
}
//sort(all(buildings));
int nodes = 0;
vvii adj = { };
vvii open(n), close(n);
loop(i, m) {
auto [y, l, r] = bridges[i];
open[l].push_back({y, i});
close[r].push_back({y, i});
}
int start = -1, end = -1;
map<ii, int> cur;
for (int i = 0; i < n; i++) {
for (auto [y, j] : open[i]) {
cur[{y, j}] = nodes++;
adj.push_back({});
}
int prevNode = nodes++;
adj.push_back({});
if (i == s) {
start = prevNode;
}
if (i == g) {
end = prevNode;
}
int prevY = 0;
for (auto [f, idx] : cur) {
auto [y, j] = f;
if (y > buildings[i].second) break;
int node = idx;
if (xs[i] != xs[ls[j]]) {
node = nodes++;
adj.push_back({});
adj[idx].push_back({node, xs[i] - xs[ls[j]]});
adj[node].push_back({idx, xs[i] - xs[ls[j]]});
}
adj[prevNode].push_back({ node, y - prevY });
adj[node].push_back({ prevNode, y - prevY });
prevY = y;
prevNode = node;
}
for (auto [y, j] : close[i]) {
cur.erase({y, j});
}
}
vb vis(nodes, false);
priority_queue<ii, vii, greater<ii>> q;
q.push({0, start});
int res = -1;
while (q.size()) {
auto [dist, node] = q.top();
q.pop();
if (node == end) {
res = dist;
break;
}
if (vis[node]) continue;
vis[node] = true;
for (auto [child, weight] : adj[node]) {
q.push({dist + weight, child});
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
24660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
24660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
