#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, -1));
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 |
23 ms |
47240 KB |
Output is correct |
2 |
Correct |
24 ms |
47300 KB |
Output is correct |
3 |
Correct |
24 ms |
47268 KB |
Output is correct |
4 |
Correct |
24 ms |
47220 KB |
Output is correct |
5 |
Correct |
25 ms |
47364 KB |
Output is correct |
6 |
Correct |
24 ms |
47316 KB |
Output is correct |
7 |
Correct |
25 ms |
47316 KB |
Output is correct |
8 |
Correct |
26 ms |
47316 KB |
Output is correct |
9 |
Correct |
25 ms |
47240 KB |
Output is correct |
10 |
Correct |
25 ms |
47272 KB |
Output is correct |
11 |
Correct |
25 ms |
47272 KB |
Output is correct |
12 |
Correct |
26 ms |
47316 KB |
Output is correct |
13 |
Correct |
25 ms |
47292 KB |
Output is correct |
14 |
Correct |
23 ms |
47316 KB |
Output is correct |
15 |
Correct |
25 ms |
47332 KB |
Output is correct |
16 |
Correct |
24 ms |
47272 KB |
Output is correct |
17 |
Correct |
24 ms |
47352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47316 KB |
Output is correct |
2 |
Correct |
25 ms |
47256 KB |
Output is correct |
3 |
Correct |
1306 ms |
119980 KB |
Output is correct |
4 |
Correct |
1192 ms |
122316 KB |
Output is correct |
5 |
Correct |
766 ms |
104980 KB |
Output is correct |
6 |
Correct |
727 ms |
100580 KB |
Output is correct |
7 |
Correct |
759 ms |
105076 KB |
Output is correct |
8 |
Correct |
1348 ms |
125512 KB |
Output is correct |
9 |
Correct |
1068 ms |
117196 KB |
Output is correct |
10 |
Correct |
1237 ms |
125832 KB |
Output is correct |
11 |
Correct |
909 ms |
105596 KB |
Output is correct |
12 |
Correct |
653 ms |
93716 KB |
Output is correct |
13 |
Correct |
1212 ms |
128604 KB |
Output is correct |
14 |
Correct |
640 ms |
92032 KB |
Output is correct |
15 |
Correct |
599 ms |
85380 KB |
Output is correct |
16 |
Correct |
559 ms |
84192 KB |
Output is correct |
17 |
Correct |
552 ms |
82348 KB |
Output is correct |
18 |
Correct |
768 ms |
101704 KB |
Output is correct |
19 |
Correct |
43 ms |
49860 KB |
Output is correct |
20 |
Correct |
263 ms |
71668 KB |
Output is correct |
21 |
Correct |
491 ms |
86516 KB |
Output is correct |
22 |
Correct |
464 ms |
86736 KB |
Output is correct |
23 |
Correct |
727 ms |
96500 KB |
Output is correct |
24 |
Correct |
509 ms |
86632 KB |
Output is correct |
25 |
Correct |
541 ms |
85256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
176 ms |
59384 KB |
Output is correct |
2 |
Correct |
1376 ms |
142156 KB |
Output is correct |
3 |
Correct |
1621 ms |
145992 KB |
Output is correct |
4 |
Correct |
1601 ms |
148464 KB |
Output is correct |
5 |
Correct |
1733 ms |
147316 KB |
Output is correct |
6 |
Correct |
1582 ms |
141696 KB |
Output is correct |
7 |
Correct |
712 ms |
99912 KB |
Output is correct |
8 |
Correct |
605 ms |
93748 KB |
Output is correct |
9 |
Correct |
1482 ms |
135552 KB |
Output is correct |
10 |
Correct |
666 ms |
95968 KB |
Output is correct |
11 |
Correct |
49 ms |
51784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
176 ms |
59384 KB |
Output is correct |
2 |
Correct |
1376 ms |
142156 KB |
Output is correct |
3 |
Correct |
1621 ms |
145992 KB |
Output is correct |
4 |
Correct |
1601 ms |
148464 KB |
Output is correct |
5 |
Correct |
1733 ms |
147316 KB |
Output is correct |
6 |
Correct |
1582 ms |
141696 KB |
Output is correct |
7 |
Correct |
712 ms |
99912 KB |
Output is correct |
8 |
Correct |
605 ms |
93748 KB |
Output is correct |
9 |
Correct |
1482 ms |
135552 KB |
Output is correct |
10 |
Correct |
666 ms |
95968 KB |
Output is correct |
11 |
Correct |
49 ms |
51784 KB |
Output is correct |
12 |
Correct |
1637 ms |
145512 KB |
Output is correct |
13 |
Correct |
1481 ms |
148464 KB |
Output is correct |
14 |
Correct |
1743 ms |
147200 KB |
Output is correct |
15 |
Correct |
1091 ms |
120984 KB |
Output is correct |
16 |
Correct |
1132 ms |
120960 KB |
Output is correct |
17 |
Correct |
1315 ms |
141040 KB |
Output is correct |
18 |
Correct |
1058 ms |
120816 KB |
Output is correct |
19 |
Correct |
1144 ms |
121044 KB |
Output is correct |
20 |
Correct |
772 ms |
98372 KB |
Output is correct |
21 |
Correct |
129 ms |
56148 KB |
Output is correct |
22 |
Correct |
1049 ms |
123624 KB |
Output is correct |
23 |
Correct |
980 ms |
117692 KB |
Output is correct |
24 |
Correct |
699 ms |
96444 KB |
Output is correct |
25 |
Correct |
904 ms |
113508 KB |
Output is correct |
26 |
Correct |
564 ms |
91812 KB |
Output is correct |
27 |
Correct |
1845 ms |
147360 KB |
Output is correct |
28 |
Correct |
1470 ms |
147116 KB |
Output is correct |
29 |
Correct |
1649 ms |
141880 KB |
Output is correct |
30 |
Correct |
764 ms |
99532 KB |
Output is correct |
31 |
Correct |
1515 ms |
135476 KB |
Output is correct |
32 |
Correct |
601 ms |
88032 KB |
Output is correct |
33 |
Correct |
603 ms |
87472 KB |
Output is correct |
34 |
Correct |
681 ms |
92764 KB |
Output is correct |
35 |
Correct |
750 ms |
97348 KB |
Output is correct |
36 |
Correct |
650 ms |
87868 KB |
Output is correct |
37 |
Correct |
492 ms |
83612 KB |
Output is correct |
38 |
Correct |
460 ms |
83692 KB |
Output is correct |
39 |
Correct |
736 ms |
93592 KB |
Output is correct |
40 |
Correct |
508 ms |
83736 KB |
Output is correct |
41 |
Correct |
558 ms |
82320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
47240 KB |
Output is correct |
2 |
Correct |
24 ms |
47300 KB |
Output is correct |
3 |
Correct |
24 ms |
47268 KB |
Output is correct |
4 |
Correct |
24 ms |
47220 KB |
Output is correct |
5 |
Correct |
25 ms |
47364 KB |
Output is correct |
6 |
Correct |
24 ms |
47316 KB |
Output is correct |
7 |
Correct |
25 ms |
47316 KB |
Output is correct |
8 |
Correct |
26 ms |
47316 KB |
Output is correct |
9 |
Correct |
25 ms |
47240 KB |
Output is correct |
10 |
Correct |
25 ms |
47272 KB |
Output is correct |
11 |
Correct |
25 ms |
47272 KB |
Output is correct |
12 |
Correct |
26 ms |
47316 KB |
Output is correct |
13 |
Correct |
25 ms |
47292 KB |
Output is correct |
14 |
Correct |
23 ms |
47316 KB |
Output is correct |
15 |
Correct |
25 ms |
47332 KB |
Output is correct |
16 |
Correct |
24 ms |
47272 KB |
Output is correct |
17 |
Correct |
24 ms |
47352 KB |
Output is correct |
18 |
Correct |
24 ms |
47316 KB |
Output is correct |
19 |
Correct |
25 ms |
47256 KB |
Output is correct |
20 |
Correct |
1306 ms |
119980 KB |
Output is correct |
21 |
Correct |
1192 ms |
122316 KB |
Output is correct |
22 |
Correct |
766 ms |
104980 KB |
Output is correct |
23 |
Correct |
727 ms |
100580 KB |
Output is correct |
24 |
Correct |
759 ms |
105076 KB |
Output is correct |
25 |
Correct |
1348 ms |
125512 KB |
Output is correct |
26 |
Correct |
1068 ms |
117196 KB |
Output is correct |
27 |
Correct |
1237 ms |
125832 KB |
Output is correct |
28 |
Correct |
909 ms |
105596 KB |
Output is correct |
29 |
Correct |
653 ms |
93716 KB |
Output is correct |
30 |
Correct |
1212 ms |
128604 KB |
Output is correct |
31 |
Correct |
640 ms |
92032 KB |
Output is correct |
32 |
Correct |
599 ms |
85380 KB |
Output is correct |
33 |
Correct |
559 ms |
84192 KB |
Output is correct |
34 |
Correct |
552 ms |
82348 KB |
Output is correct |
35 |
Correct |
768 ms |
101704 KB |
Output is correct |
36 |
Correct |
43 ms |
49860 KB |
Output is correct |
37 |
Correct |
263 ms |
71668 KB |
Output is correct |
38 |
Correct |
491 ms |
86516 KB |
Output is correct |
39 |
Correct |
464 ms |
86736 KB |
Output is correct |
40 |
Correct |
727 ms |
96500 KB |
Output is correct |
41 |
Correct |
509 ms |
86632 KB |
Output is correct |
42 |
Correct |
541 ms |
85256 KB |
Output is correct |
43 |
Correct |
176 ms |
59384 KB |
Output is correct |
44 |
Correct |
1376 ms |
142156 KB |
Output is correct |
45 |
Correct |
1621 ms |
145992 KB |
Output is correct |
46 |
Correct |
1601 ms |
148464 KB |
Output is correct |
47 |
Correct |
1733 ms |
147316 KB |
Output is correct |
48 |
Correct |
1582 ms |
141696 KB |
Output is correct |
49 |
Correct |
712 ms |
99912 KB |
Output is correct |
50 |
Correct |
605 ms |
93748 KB |
Output is correct |
51 |
Correct |
1482 ms |
135552 KB |
Output is correct |
52 |
Correct |
666 ms |
95968 KB |
Output is correct |
53 |
Correct |
49 ms |
51784 KB |
Output is correct |
54 |
Correct |
1637 ms |
145512 KB |
Output is correct |
55 |
Correct |
1481 ms |
148464 KB |
Output is correct |
56 |
Correct |
1743 ms |
147200 KB |
Output is correct |
57 |
Correct |
1091 ms |
120984 KB |
Output is correct |
58 |
Correct |
1132 ms |
120960 KB |
Output is correct |
59 |
Correct |
1315 ms |
141040 KB |
Output is correct |
60 |
Correct |
1058 ms |
120816 KB |
Output is correct |
61 |
Correct |
1144 ms |
121044 KB |
Output is correct |
62 |
Correct |
772 ms |
98372 KB |
Output is correct |
63 |
Correct |
129 ms |
56148 KB |
Output is correct |
64 |
Correct |
1049 ms |
123624 KB |
Output is correct |
65 |
Correct |
980 ms |
117692 KB |
Output is correct |
66 |
Correct |
699 ms |
96444 KB |
Output is correct |
67 |
Correct |
904 ms |
113508 KB |
Output is correct |
68 |
Correct |
564 ms |
91812 KB |
Output is correct |
69 |
Correct |
1845 ms |
147360 KB |
Output is correct |
70 |
Correct |
1470 ms |
147116 KB |
Output is correct |
71 |
Correct |
1649 ms |
141880 KB |
Output is correct |
72 |
Correct |
764 ms |
99532 KB |
Output is correct |
73 |
Correct |
1515 ms |
135476 KB |
Output is correct |
74 |
Correct |
601 ms |
88032 KB |
Output is correct |
75 |
Correct |
603 ms |
87472 KB |
Output is correct |
76 |
Correct |
681 ms |
92764 KB |
Output is correct |
77 |
Correct |
750 ms |
97348 KB |
Output is correct |
78 |
Correct |
650 ms |
87868 KB |
Output is correct |
79 |
Correct |
492 ms |
83612 KB |
Output is correct |
80 |
Correct |
460 ms |
83692 KB |
Output is correct |
81 |
Correct |
736 ms |
93592 KB |
Output is correct |
82 |
Correct |
508 ms |
83736 KB |
Output is correct |
83 |
Correct |
558 ms |
82320 KB |
Output is correct |
84 |
Correct |
151 ms |
57132 KB |
Output is correct |
85 |
Correct |
1697 ms |
149948 KB |
Output is correct |
86 |
Correct |
1974 ms |
164088 KB |
Output is correct |
87 |
Correct |
137 ms |
60740 KB |
Output is correct |
88 |
Correct |
168 ms |
61288 KB |
Output is correct |
89 |
Correct |
169 ms |
60616 KB |
Output is correct |
90 |
Correct |
61 ms |
50864 KB |
Output is correct |
91 |
Correct |
26 ms |
47376 KB |
Output is correct |
92 |
Correct |
64 ms |
51164 KB |
Output is correct |
93 |
Correct |
534 ms |
85476 KB |
Output is correct |
94 |
Correct |
126 ms |
59196 KB |
Output is correct |
95 |
Correct |
1109 ms |
131396 KB |
Output is correct |
96 |
Correct |
992 ms |
121928 KB |
Output is correct |
97 |
Correct |
716 ms |
100104 KB |
Output is correct |
98 |
Correct |
900 ms |
117084 KB |
Output is correct |
99 |
Correct |
2310 ms |
182152 KB |
Output is correct |
100 |
Correct |
1614 ms |
152364 KB |
Output is correct |
101 |
Correct |
1849 ms |
156664 KB |
Output is correct |
102 |
Correct |
762 ms |
102788 KB |
Output is correct |
103 |
Correct |
613 ms |
91040 KB |
Output is correct |
104 |
Correct |
578 ms |
90624 KB |
Output is correct |
105 |
Correct |
684 ms |
95648 KB |
Output is correct |
106 |
Correct |
656 ms |
93212 KB |
Output is correct |
107 |
Correct |
653 ms |
93180 KB |
Output is correct |
108 |
Correct |
110 ms |
55040 KB |
Output is correct |
109 |
Correct |
1318 ms |
126792 KB |
Output is correct |
110 |
Correct |
1421 ms |
151408 KB |
Output is correct |
111 |
Correct |
1408 ms |
151276 KB |
Output is correct |
112 |
Correct |
741 ms |
98424 KB |
Output is correct |
113 |
Correct |
711 ms |
95268 KB |
Output is correct |