#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 |
47316 KB |
Output is correct |
2 |
Correct |
27 ms |
47212 KB |
Output is correct |
3 |
Correct |
24 ms |
47316 KB |
Output is correct |
4 |
Correct |
24 ms |
47228 KB |
Output is correct |
5 |
Correct |
24 ms |
47244 KB |
Output is correct |
6 |
Correct |
24 ms |
47316 KB |
Output is correct |
7 |
Correct |
23 ms |
47268 KB |
Output is correct |
8 |
Correct |
24 ms |
47284 KB |
Output is correct |
9 |
Correct |
24 ms |
47316 KB |
Output is correct |
10 |
Correct |
25 ms |
47360 KB |
Output is correct |
11 |
Correct |
38 ms |
47304 KB |
Output is correct |
12 |
Incorrect |
25 ms |
47316 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
47288 KB |
Output is correct |
2 |
Correct |
25 ms |
47312 KB |
Output is correct |
3 |
Correct |
1249 ms |
119888 KB |
Output is correct |
4 |
Correct |
1092 ms |
122268 KB |
Output is correct |
5 |
Correct |
711 ms |
104856 KB |
Output is correct |
6 |
Correct |
675 ms |
100496 KB |
Output is correct |
7 |
Correct |
732 ms |
105132 KB |
Output is correct |
8 |
Correct |
1365 ms |
125384 KB |
Output is correct |
9 |
Correct |
980 ms |
117088 KB |
Output is correct |
10 |
Incorrect |
1147 ms |
125804 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
190 ms |
58700 KB |
Output is correct |
2 |
Correct |
1361 ms |
142224 KB |
Output is correct |
3 |
Correct |
1642 ms |
145996 KB |
Output is correct |
4 |
Correct |
1593 ms |
148576 KB |
Output is correct |
5 |
Correct |
1725 ms |
147272 KB |
Output is correct |
6 |
Correct |
1565 ms |
141884 KB |
Output is correct |
7 |
Correct |
693 ms |
99956 KB |
Output is correct |
8 |
Correct |
590 ms |
90796 KB |
Output is correct |
9 |
Correct |
1457 ms |
135420 KB |
Output is correct |
10 |
Correct |
622 ms |
96352 KB |
Output is correct |
11 |
Correct |
33 ms |
48464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
190 ms |
58700 KB |
Output is correct |
2 |
Correct |
1361 ms |
142224 KB |
Output is correct |
3 |
Correct |
1642 ms |
145996 KB |
Output is correct |
4 |
Correct |
1593 ms |
148576 KB |
Output is correct |
5 |
Correct |
1725 ms |
147272 KB |
Output is correct |
6 |
Correct |
1565 ms |
141884 KB |
Output is correct |
7 |
Correct |
693 ms |
99956 KB |
Output is correct |
8 |
Correct |
590 ms |
90796 KB |
Output is correct |
9 |
Correct |
1457 ms |
135420 KB |
Output is correct |
10 |
Correct |
622 ms |
96352 KB |
Output is correct |
11 |
Correct |
33 ms |
48464 KB |
Output is correct |
12 |
Correct |
1654 ms |
145764 KB |
Output is correct |
13 |
Correct |
1481 ms |
148452 KB |
Output is correct |
14 |
Correct |
1695 ms |
147376 KB |
Output is correct |
15 |
Correct |
1062 ms |
120828 KB |
Output is correct |
16 |
Correct |
1053 ms |
121036 KB |
Output is correct |
17 |
Correct |
1266 ms |
141128 KB |
Output is correct |
18 |
Correct |
1018 ms |
120784 KB |
Output is correct |
19 |
Correct |
1087 ms |
120996 KB |
Output is correct |
20 |
Correct |
715 ms |
98544 KB |
Output is correct |
21 |
Correct |
51 ms |
50636 KB |
Output is correct |
22 |
Correct |
995 ms |
123528 KB |
Output is correct |
23 |
Correct |
905 ms |
117700 KB |
Output is correct |
24 |
Correct |
643 ms |
96528 KB |
Output is correct |
25 |
Correct |
866 ms |
113612 KB |
Output is correct |
26 |
Correct |
507 ms |
87112 KB |
Output is correct |
27 |
Correct |
1705 ms |
147328 KB |
Output is correct |
28 |
Correct |
1478 ms |
147124 KB |
Output is correct |
29 |
Correct |
1696 ms |
141756 KB |
Output is correct |
30 |
Correct |
688 ms |
99632 KB |
Output is correct |
31 |
Correct |
1427 ms |
135516 KB |
Output is correct |
32 |
Correct |
567 ms |
88252 KB |
Output is correct |
33 |
Correct |
556 ms |
87576 KB |
Output is correct |
34 |
Correct |
655 ms |
92696 KB |
Output is correct |
35 |
Correct |
705 ms |
97128 KB |
Output is correct |
36 |
Correct |
607 ms |
87844 KB |
Output is correct |
37 |
Correct |
462 ms |
81348 KB |
Output is correct |
38 |
Correct |
435 ms |
80608 KB |
Output is correct |
39 |
Correct |
664 ms |
93104 KB |
Output is correct |
40 |
Correct |
539 ms |
81704 KB |
Output is correct |
41 |
Correct |
512 ms |
81084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47316 KB |
Output is correct |
2 |
Correct |
27 ms |
47212 KB |
Output is correct |
3 |
Correct |
24 ms |
47316 KB |
Output is correct |
4 |
Correct |
24 ms |
47228 KB |
Output is correct |
5 |
Correct |
24 ms |
47244 KB |
Output is correct |
6 |
Correct |
24 ms |
47316 KB |
Output is correct |
7 |
Correct |
23 ms |
47268 KB |
Output is correct |
8 |
Correct |
24 ms |
47284 KB |
Output is correct |
9 |
Correct |
24 ms |
47316 KB |
Output is correct |
10 |
Correct |
25 ms |
47360 KB |
Output is correct |
11 |
Correct |
38 ms |
47304 KB |
Output is correct |
12 |
Incorrect |
25 ms |
47316 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |