#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define eb emplace_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const ll INF =1e18;
#ifdef LOCAL
#include "../../../../../MixedFunc/pretty_debug.h"
#else
#define debug(...) //ignore
#endif
template<class T>
auto dijkstra(int source, vector<vector<pair<int, T>>> &g) {
int n = sz(g);
vector<T> dist(n, numeric_limits<T>::max());
vector<pair<int,T> > dad(n, {-1, 0});
priority_queue<pair<T,int> > pq;
dist[source] = 0;
pq.emplace(0,source);
while(!pq.empty()) {
T d; int x;
tie(d,x) = pq.top();
d = -d;
pq.pop();
if(d > dist[x]) continue;
for(auto [y,w] : g[x]) {
if(dist[y] > d + w) {
dist[y] = d + w;
dad[y] = {x, w};
pq.emplace(-dist[y], y);
}
}
}
return pair{dist, dad};
}
ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
int n = sz(x), m = sz(l);
debug(n,m);
auto st12 = [&](){
map<ll, map<ll, int> > V;
map<int, pair<ll,ll>> iV;
vector<vector<pair<int,ll>>> E;
auto at = [&](int i, int h) {
if (!V[x[i]].count(h)) {
V[x[i]][h] = sz(E);
iV[sz(E)] = {x[i],h};
E.emplace_back();
}
return V[x[i]][h];
};
auto edge = [&](int a, int b, ll c) {
E[a].emplace_back(b,c);
E[b].emplace_back(a,c);
};
auto edges = [&](map<ll,int> vert) {
pair<ll,int> a = *vert.begin();
vert.erase(vert.begin());
for(auto b : vert) {
edge(a.second, b.second, b.first-a.first);
a = b;
}
};
at(s,0);
at(g,0);
rep(i,0,m) {
l[i], r[i], y[i];
map<ll, int> vert;
vert[x[l[i]]] = at(l[i], y[i]);
vert[x[r[i]]] = at(r[i], y[i]);
// temporary
rep(j,l[i]+1, r[i]) if(h[j] >= y[i])
vert[x[j]] = at(j, y[i]);
edges(vert);
}
for(auto v: V) edges(v.second);
debug(sz(E))
auto[dist, dad] = dijkstra(at(s,0),E);
for(int q = at(g,0); dad[q].first != -1; q = dad[q].first) {
debug(iV[q]);
}
ll ans = dist[at(g, 0)];
if (ans >= INF) ans = -1;
return ans;
};
auto st34 = [&](){
vector<vi> start(n), end(n);
rep(i,0,m) {
start[l[i]].eb(y[i]);
end[r[i]].eb(y[i]);
}
start[n-1].eb(0);
end[0].eb(0);
// cost[h] = get to dp[h]
map<int, ll> cost;
map<int, ll> cnt;
cost[0] = 0;
cnt[0] = 1;
debug(n);
rep(i,0,n) {
debug(i, cost);
for(int H : start[i]) {
if(cnt[H]++ == 0) {
debug("add", H);
ll c = INF;
auto C = [&](auto p) { return p.second + abs(p.first - H); };
auto it = cost.lower_bound(H);
if(it != cost.end()) c = min(c, C(*it));
if(it != cost.begin()) c = min(c, C(*--it));
cost[H] = c;
}
}
for(int H : end[i]) {
if(--cnt[H] == 0) {
debug("rem", H);
cost.erase(H);
}
}
}
debug(cost)
debug(x[n-1] - x[0]);
ll ans = cost[0] + x[n-1]-x[0];
if (ans >= INF) ans = -1;
return ans;
};
if (s == 0 && g == n-1) return st34();
else return st12();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
504 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
3 ms |
504 KB |
Output is correct |
8 |
Correct |
3 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
380 KB |
Output is correct |
10 |
Correct |
3 ms |
504 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
256 KB |
Output is correct |
17 |
Correct |
3 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2487 ms |
203408 KB |
Output is correct |
4 |
Correct |
2235 ms |
212720 KB |
Output is correct |
5 |
Correct |
1719 ms |
182904 KB |
Output is correct |
6 |
Correct |
2416 ms |
161036 KB |
Output is correct |
7 |
Correct |
1718 ms |
183236 KB |
Output is correct |
8 |
Correct |
3285 ms |
260720 KB |
Output is correct |
9 |
Correct |
1850 ms |
182132 KB |
Output is correct |
10 |
Correct |
3257 ms |
296692 KB |
Output is correct |
11 |
Correct |
1203 ms |
108916 KB |
Output is correct |
12 |
Correct |
237 ms |
25408 KB |
Output is correct |
13 |
Correct |
267 ms |
25464 KB |
Output is correct |
14 |
Execution timed out |
4033 ms |
44700 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
3708 KB |
Output is correct |
2 |
Correct |
233 ms |
12112 KB |
Output is correct |
3 |
Correct |
253 ms |
13504 KB |
Output is correct |
4 |
Correct |
314 ms |
23292 KB |
Output is correct |
5 |
Correct |
379 ms |
28024 KB |
Output is correct |
6 |
Correct |
370 ms |
24772 KB |
Output is correct |
7 |
Correct |
145 ms |
16888 KB |
Output is correct |
8 |
Correct |
238 ms |
25564 KB |
Output is correct |
9 |
Correct |
381 ms |
27384 KB |
Output is correct |
10 |
Correct |
226 ms |
22300 KB |
Output is correct |
11 |
Correct |
19 ms |
4236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
3708 KB |
Output is correct |
2 |
Correct |
233 ms |
12112 KB |
Output is correct |
3 |
Correct |
253 ms |
13504 KB |
Output is correct |
4 |
Correct |
314 ms |
23292 KB |
Output is correct |
5 |
Correct |
379 ms |
28024 KB |
Output is correct |
6 |
Correct |
370 ms |
24772 KB |
Output is correct |
7 |
Correct |
145 ms |
16888 KB |
Output is correct |
8 |
Correct |
238 ms |
25564 KB |
Output is correct |
9 |
Correct |
381 ms |
27384 KB |
Output is correct |
10 |
Correct |
226 ms |
22300 KB |
Output is correct |
11 |
Correct |
19 ms |
4236 KB |
Output is correct |
12 |
Correct |
257 ms |
13456 KB |
Output is correct |
13 |
Correct |
322 ms |
23260 KB |
Output is correct |
14 |
Correct |
397 ms |
27844 KB |
Output is correct |
15 |
Correct |
196 ms |
18964 KB |
Output is correct |
16 |
Correct |
206 ms |
18936 KB |
Output is correct |
17 |
Correct |
240 ms |
18980 KB |
Output is correct |
18 |
Correct |
203 ms |
18808 KB |
Output is correct |
19 |
Correct |
197 ms |
19088 KB |
Output is correct |
20 |
Correct |
164 ms |
16784 KB |
Output is correct |
21 |
Correct |
44 ms |
8696 KB |
Output is correct |
22 |
Correct |
197 ms |
19192 KB |
Output is correct |
23 |
Correct |
200 ms |
19704 KB |
Output is correct |
24 |
Correct |
219 ms |
20472 KB |
Output is correct |
25 |
Correct |
202 ms |
20408 KB |
Output is correct |
26 |
Correct |
217 ms |
22392 KB |
Output is correct |
27 |
Correct |
387 ms |
27376 KB |
Output is correct |
28 |
Correct |
278 ms |
23088 KB |
Output is correct |
29 |
Correct |
367 ms |
24696 KB |
Output is correct |
30 |
Correct |
176 ms |
16916 KB |
Output is correct |
31 |
Correct |
426 ms |
27380 KB |
Output is correct |
32 |
Correct |
150 ms |
18552 KB |
Output is correct |
33 |
Correct |
153 ms |
20188 KB |
Output is correct |
34 |
Correct |
192 ms |
20640 KB |
Output is correct |
35 |
Correct |
176 ms |
18796 KB |
Output is correct |
36 |
Correct |
144 ms |
17500 KB |
Output is correct |
37 |
Correct |
111 ms |
14900 KB |
Output is correct |
38 |
Correct |
130 ms |
18352 KB |
Output is correct |
39 |
Correct |
240 ms |
23088 KB |
Output is correct |
40 |
Correct |
133 ms |
17784 KB |
Output is correct |
41 |
Correct |
123 ms |
15864 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
504 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
3 ms |
504 KB |
Output is correct |
8 |
Correct |
3 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
380 KB |
Output is correct |
10 |
Correct |
3 ms |
504 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
256 KB |
Output is correct |
17 |
Correct |
3 ms |
256 KB |
Output is correct |
18 |
Correct |
2 ms |
256 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2487 ms |
203408 KB |
Output is correct |
21 |
Correct |
2235 ms |
212720 KB |
Output is correct |
22 |
Correct |
1719 ms |
182904 KB |
Output is correct |
23 |
Correct |
2416 ms |
161036 KB |
Output is correct |
24 |
Correct |
1718 ms |
183236 KB |
Output is correct |
25 |
Correct |
3285 ms |
260720 KB |
Output is correct |
26 |
Correct |
1850 ms |
182132 KB |
Output is correct |
27 |
Correct |
3257 ms |
296692 KB |
Output is correct |
28 |
Correct |
1203 ms |
108916 KB |
Output is correct |
29 |
Correct |
237 ms |
25408 KB |
Output is correct |
30 |
Correct |
267 ms |
25464 KB |
Output is correct |
31 |
Execution timed out |
4033 ms |
44700 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |