#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18L + 20;
const int maxN = 1e5 + 20;
const int max_nodes = maxN * 12;
int X[maxN];
int Y[maxN * 2];
int H[maxN * 2];
int L[maxN];
int R[maxN];
pair<int, int> orderY[maxN * 2];
vector<int> qadd[maxN];
vector<int> qrem[maxN];
vector<int> row[maxN * 2];
vector<int> col[maxN];
long long dist[max_nodes];
vector<pair<int, int>> adj[max_nodes];
map<pair<int, int>, int> points;
int node_cnt;
int get_id(int i, int j) {
auto it = points.find(make_pair(i, j));
if (it == points.end()) {
return points[make_pair(i, j)] = ++node_cnt;
}
else {
return it->second;
}
}
void add_edge(int i1, int j1, int i2, int j2) {
int u = get_id(i1, j1);
int v = get_id(i2, j2);
int w = abs(X[i1] - X[i2]) + abs(Y[j1] - Y[j2]);
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
long long min_distance(vector<int> _X, vector<int> _H, vector<int> _L, vector<int> _R, vector<int> _Y, int _S, int _T) {
int N = _X.size();
int M = _L.size();
for (int i = 1; i <= N; i++) {
X[i] = _X[i - 1];
}
for (int i = 1; i <= M; i++) {
orderY[i] = make_pair(_Y[i - 1], i);
}
for (int i = M + 1; i <= M + N; i++) {
orderY[i] = make_pair(_H[i - M - 1], i);
}
sort(orderY + 1, orderY + N + M + 1);
for (int i = 1; i <= N + M; i++) {
Y[i] = orderY[i].first;
H[orderY[i].second] = i;
}
for (int i = 1; i <= M; i++) {
L[i] = _L[i - 1] + 1;
R[i] = _R[i - 1] + 1;
qadd[L[i]].push_back(i);
qrem[R[i]].push_back(i);
}
set<int> walks;
for (int i = 1; i <= N; i++) {
col[i].push_back(0);
col[i].push_back(H[M + i]);
for (auto id: qadd[i]) {
walks.insert(H[id]);
}
for (auto id: qadd[i]) {
col[i].push_back(H[id]);
row[H[id]].push_back(i);
auto it = walks.lower_bound(H[id]);
if (it != walks.begin()) {
it--;
col[i].push_back(*it);
row[*it].push_back(i);
}
}
for (auto id: qrem[i]) {
col[i].push_back(H[id]);
row[H[id]].push_back(i);
auto it = walks.lower_bound(H[id]);
if (it != walks.begin()) {
it--;
col[i].push_back(*it);
row[*it].push_back(i);
}
}
}
for (int i = 1; i <= N; i++) {
sort(col[i].begin(), col[i].end());
//col[i].erase(unique(col[i].begin(), col[i].end()), col[i].end());
for (int j = 0; j < (int)col[i].size() - 1; j++) {
add_edge(i, col[i][j], i, col[i][j + 1]);
}
}
for (int i = 1; i <= M; i++) {
sort(row[H[i]].begin(), row[H[i]].end());
//row[H[i]].erase(unique(row[H[i]].begin(), row[H[i]].end()), row[H[i]].end());
for (int j = 0; j < (int)row[H[i]].size() - 1; j++) {
add_edge(row[H[i]][j], H[i], row[H[i]][j + 1], H[i]);
}
}
int S = get_id(_S + 1, 0);
int T = get_id(_T + 1, 0);
for (int i = 1; i <= node_cnt; i++) {
dist[i] = inf;
}
dist[S] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> Q;
Q.emplace(0, S);
while (!Q.empty()) {
int u = Q.top().second;
if (Q.top().first != dist[u]) {
Q.pop();
continue;
}
Q.pop();
for (auto e: adj[u]) {
int v = e.first;
int w = e.second;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
Q.emplace(dist[v], v);
}
}
}
if (dist[T] == inf) {
return -1;
}
else {
return dist[T];
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
40148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
40248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
336 ms |
80592 KB |
Output is correct |
| 2 |
Correct |
841 ms |
116680 KB |
Output is correct |
| 3 |
Correct |
849 ms |
119884 KB |
Output is correct |
| 4 |
Incorrect |
1138 ms |
147408 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
336 ms |
80592 KB |
Output is correct |
| 2 |
Correct |
841 ms |
116680 KB |
Output is correct |
| 3 |
Correct |
849 ms |
119884 KB |
Output is correct |
| 4 |
Incorrect |
1138 ms |
147408 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
40148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
