#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
constexpr ll INF = 4e18;
constexpr int MAXN = 2002000;
int n, m;
vector<int> X, H, L, R, Y;
map<int, vector<pii>> Z;
struct Event{
int l, r, y, typ;
Event(){}
Event(int _l, int _r, int _y, int _typ): l(_l), r(_r), y(_y), typ(_typ) {}
};
struct Graph{
map<pii, int> V;
vector<pii> adj[MAXN];
ll dist[MAXN];
int sz;
int add_vertex(int x, int y){
pii p(x, y);
if (V[p]) return V[p];
//printf(" add vertex: %d %d\n", x, y);
V[p] = ++sz;
assert(sz<MAXN);
return sz;
}
void add_edge(int x1, int y1, int x2, int y2){
//printf(" add edge: %d %d <-> %d %d\n", x1, y1, x2, y2);
pii p1(x1, y1), p2(x2, y2);
int i1 = add_vertex(x1, y1), i2 = add_vertex(x2, y2);
int d = abs(x1-x2) + abs(y1-y2);
adj[i1].emplace_back(i2, d);
adj[i2].emplace_back(i1, d);
}
vector<pii> get_vertex(){
vector<pii> ret;
for (auto &[x, y]:V) ret.push_back(x);
return ret;
}
ll calc(int s, int e){
fill(dist+1, dist+sz+1, INF);
dist[s] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.emplace(dist[s], s);
while(!pq.empty()){
auto [d, cur] = pq.top(); pq.pop();
if (d > dist[cur]) continue;
assert(dist[cur] == d);
for (auto &[nxt, e]:adj[cur]) if (dist[nxt] > dist[cur] + e){
dist[nxt] = dist[cur] + e;
pq.emplace(dist[nxt], nxt);
}
}
return dist[e]==INF?-1:dist[e];
}
}G;
int h(int x){
int idx = lower_bound(X.begin(), X.end(), x) - X.begin();
return H[idx];
}
void f(int x){
//printf("\n f %d\n", x);
vector<Event> E;
for (int i=0;i<n;i++) E.emplace_back(X[i], X[i], H[i], 0);
for (int i=0;i<m;i++) E.emplace_back(L[i], R[i], Y[i], -1);
sort(E.begin(), E.end(), [&](const Event &a, const Event &b){return tie(a.y, a.typ) > tie(b.y, b.typ);});
set<int> st;
for (auto &[l, r, y, typ]:E){
//printf(" %d %d %d %d\n", l, r, y, typ);
if (typ==0) {st.insert(l); continue;}
if (r<x || x<l) continue;
auto iterL = st.upper_bound(x);
auto iterR = st.lower_bound(x);
if (iterL!=st.begin() && *prev(iterL) >= l) G.add_vertex(*--iterL, y);
if (iterR!=st.end() && *iterR <= r) G.add_vertex(*iterR, y);
}
}
void add_vertical(){
//printf("\n vertical\n");
auto V = G.get_vertex();
vector<Event> E;
multiset<pii> st;
for (int i=0;i<m;i++){
E.emplace_back(L[i], Y[i], i, 0);
E.emplace_back(R[i], Y[i], i, 2);
}
for (auto &[x, y]:V) E.emplace_back(x, y, 0, 1);
sort(E.begin(), E.end(), [&](const Event &a, const Event &b){return tie(a.l, a.typ) < tie(b.l, b.typ);});
for (auto &[x, y, i, typ]:E){
if (typ==0) st.emplace(y, i);
else if (typ==2) st.erase(st.find(pii(y, i)));
else{
auto iter = st.lower_bound(pii(y, i));
if (y==0){
if (iter!=st.end() && iter->first <= h(x)) G.add_edge(x, y, x, iter->first);
continue;
}
assert(iter!=st.end());
if (iter!=st.begin()) G.add_edge(x, y, x, prev(iter)->first);
if (next(iter)!=st.end() && next(iter)->first <= h(x)) G.add_edge(x, y, x, next(iter)->first);
}
}
}
void add_horizontal(){
//printf("\n horizontal\n");
auto V = G.get_vertex();
sort(V.begin(), V.end(), [&](pii x, pii y){return tie(x.second, x.first) < tie(y.second, y.first);});
for (int i=1;i<(int)V.size();i++) if (V[i-1].second == V[i].second){
int x1 = V[i-1].first, x2 = V[i].first, y = V[i].second;
auto iter = lower_bound(Z[y].begin(), Z[y].end(), pii(x2, y));
if (iter==Z[y].begin()) continue;
--iter;
if (iter->first <= x1 && x2 <= iter->second) G.add_edge(x1, y, x2, y);
}
}
long long min_distance(std::vector<int> X, std::vector<int> H, std::vector<int> L, std::vector<int> R, std::vector<int> Y, int P1, int P2) {
n = X.size(); m = L.size();
P1 = X[P1], P2 = X[P2];
for (auto &x:L) x = X[x];
for (auto &x:R) x = X[x];
::X = X, ::H = H, ::L = L, ::R = R, ::Y = Y;
for (int i=0;i<m;i++){
Z[Y[i]].emplace_back(L[i], R[i]);
}
for (auto iter=Z.begin();iter!=Z.end();iter++) sort(iter->second.begin(), iter->second.end());
G.add_vertex(P1, 0);
G.add_vertex(P2, 0);
for (int i=0;i<m;i++){
G.add_vertex(L[i], Y[i]);
G.add_vertex(R[i], Y[i]);
}
f(P1); f(P2);
add_vertical();
add_horizontal();
return G.calc(1, 2);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47232 KB |
Output is correct |
2 |
Correct |
24 ms |
47316 KB |
Output is correct |
3 |
Correct |
23 ms |
47300 KB |
Output is correct |
4 |
Correct |
23 ms |
47308 KB |
Output is correct |
5 |
Correct |
23 ms |
47320 KB |
Output is correct |
6 |
Correct |
23 ms |
47316 KB |
Output is correct |
7 |
Correct |
23 ms |
47316 KB |
Output is correct |
8 |
Correct |
25 ms |
47312 KB |
Output is correct |
9 |
Correct |
25 ms |
47308 KB |
Output is correct |
10 |
Correct |
26 ms |
47316 KB |
Output is correct |
11 |
Correct |
26 ms |
47308 KB |
Output is correct |
12 |
Incorrect |
25 ms |
47356 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47228 KB |
Output is correct |
2 |
Correct |
23 ms |
47308 KB |
Output is correct |
3 |
Correct |
1327 ms |
121876 KB |
Output is correct |
4 |
Correct |
1190 ms |
126324 KB |
Output is correct |
5 |
Correct |
784 ms |
108456 KB |
Output is correct |
6 |
Correct |
782 ms |
104224 KB |
Output is correct |
7 |
Correct |
792 ms |
108640 KB |
Output is correct |
8 |
Correct |
1406 ms |
127644 KB |
Output is correct |
9 |
Correct |
1112 ms |
120728 KB |
Output is correct |
10 |
Correct |
1241 ms |
129788 KB |
Output is correct |
11 |
Correct |
982 ms |
108364 KB |
Output is correct |
12 |
Correct |
695 ms |
97864 KB |
Output is correct |
13 |
Correct |
1250 ms |
132352 KB |
Output is correct |
14 |
Correct |
669 ms |
95652 KB |
Output is correct |
15 |
Correct |
648 ms |
88688 KB |
Output is correct |
16 |
Correct |
590 ms |
87144 KB |
Output is correct |
17 |
Incorrect |
562 ms |
84832 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
226 ms |
60004 KB |
Output is correct |
2 |
Correct |
1398 ms |
143940 KB |
Output is correct |
3 |
Correct |
1658 ms |
148020 KB |
Output is correct |
4 |
Correct |
1692 ms |
152680 KB |
Output is correct |
5 |
Correct |
1810 ms |
151428 KB |
Output is correct |
6 |
Correct |
1729 ms |
146028 KB |
Output is correct |
7 |
Correct |
881 ms |
102952 KB |
Output is correct |
8 |
Correct |
674 ms |
97892 KB |
Output is correct |
9 |
Correct |
1534 ms |
139552 KB |
Output is correct |
10 |
Correct |
689 ms |
99516 KB |
Output is correct |
11 |
Correct |
50 ms |
52584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
226 ms |
60004 KB |
Output is correct |
2 |
Correct |
1398 ms |
143940 KB |
Output is correct |
3 |
Correct |
1658 ms |
148020 KB |
Output is correct |
4 |
Correct |
1692 ms |
152680 KB |
Output is correct |
5 |
Correct |
1810 ms |
151428 KB |
Output is correct |
6 |
Correct |
1729 ms |
146028 KB |
Output is correct |
7 |
Correct |
881 ms |
102952 KB |
Output is correct |
8 |
Correct |
674 ms |
97892 KB |
Output is correct |
9 |
Correct |
1534 ms |
139552 KB |
Output is correct |
10 |
Correct |
689 ms |
99516 KB |
Output is correct |
11 |
Correct |
50 ms |
52584 KB |
Output is correct |
12 |
Correct |
1671 ms |
147904 KB |
Output is correct |
13 |
Correct |
1559 ms |
152380 KB |
Output is correct |
14 |
Correct |
1859 ms |
151368 KB |
Output is correct |
15 |
Correct |
1061 ms |
124788 KB |
Output is correct |
16 |
Correct |
1161 ms |
125156 KB |
Output is correct |
17 |
Correct |
1365 ms |
145144 KB |
Output is correct |
18 |
Correct |
1149 ms |
124740 KB |
Output is correct |
19 |
Correct |
1271 ms |
124980 KB |
Output is correct |
20 |
Correct |
818 ms |
101388 KB |
Output is correct |
21 |
Correct |
126 ms |
58192 KB |
Output is correct |
22 |
Correct |
1049 ms |
127132 KB |
Output is correct |
23 |
Correct |
988 ms |
121524 KB |
Output is correct |
24 |
Correct |
740 ms |
100264 KB |
Output is correct |
25 |
Correct |
938 ms |
117216 KB |
Output is correct |
26 |
Correct |
601 ms |
95660 KB |
Output is correct |
27 |
Correct |
1832 ms |
151368 KB |
Output is correct |
28 |
Correct |
1506 ms |
151240 KB |
Output is correct |
29 |
Correct |
1644 ms |
145664 KB |
Output is correct |
30 |
Correct |
782 ms |
102612 KB |
Output is correct |
31 |
Correct |
1545 ms |
139520 KB |
Output is correct |
32 |
Correct |
656 ms |
91308 KB |
Output is correct |
33 |
Correct |
612 ms |
90708 KB |
Output is correct |
34 |
Correct |
700 ms |
95920 KB |
Output is correct |
35 |
Correct |
790 ms |
100484 KB |
Output is correct |
36 |
Correct |
668 ms |
90948 KB |
Output is correct |
37 |
Correct |
506 ms |
86556 KB |
Output is correct |
38 |
Correct |
464 ms |
86672 KB |
Output is correct |
39 |
Correct |
739 ms |
96528 KB |
Output is correct |
40 |
Correct |
525 ms |
86596 KB |
Output is correct |
41 |
Correct |
552 ms |
85116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47232 KB |
Output is correct |
2 |
Correct |
24 ms |
47316 KB |
Output is correct |
3 |
Correct |
23 ms |
47300 KB |
Output is correct |
4 |
Correct |
23 ms |
47308 KB |
Output is correct |
5 |
Correct |
23 ms |
47320 KB |
Output is correct |
6 |
Correct |
23 ms |
47316 KB |
Output is correct |
7 |
Correct |
23 ms |
47316 KB |
Output is correct |
8 |
Correct |
25 ms |
47312 KB |
Output is correct |
9 |
Correct |
25 ms |
47308 KB |
Output is correct |
10 |
Correct |
26 ms |
47316 KB |
Output is correct |
11 |
Correct |
26 ms |
47308 KB |
Output is correct |
12 |
Incorrect |
25 ms |
47356 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |