#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e6+6;
const ll inf = 1e18;
ll dis[N];
int par[N];
vector<pair<int, ll> > G[N];
map<pair<int,int>, int> mp;
ll dij(int s, int e, int n)
{
for(int i = 0; i < n; i++)
dis[i] = inf, par[i] = -1;
dis[s] = 0;
set<pair<ll, int> > st;
for(int i = 0; i < n; i ++)
st.insert({dis[i], i});
while(st.size())
{
int u = st.begin()->second;
st.erase(st.begin());
for(auto e : G[u]) {
int v = e.first, w = e.second;
if(dis[u] + w < dis[v]) {
st.erase({dis[v], v});
dis[v] = dis[u] + w;
par[v] = u;
st.insert({dis[v], v});
}
}
}
return dis[e];
}
#define F first
#define S second
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
vector<pair<int, pair<int,int> > > skywalks;
for(int i = 0; i < l.size(); i++)
skywalks.push_back({y[i], {l[i], r[i]}});
sort(skywalks.begin(), skywalks.end());
int n = x.size();
vector<int> high(x.size(), 0);
for(int i = 0; i < n; i ++)
mp[{x[i], 0}] = i;
set<int> st;
for(int i = 0; i < n; i ++)
st.insert(i);
for(int i = 0; i < skywalks.size(); i++)
{
int f = skywalks[i].S.F, s = skywalks[i].S.S, d = skywalks[i].F;
vector<int> nv, rem;
for(auto it = st.lower_bound(f); it!= st.end() && *it <= s; it++){
int b = *it;
if(h[b] < d){
rem.push_back(b);
continue;
}
nv.push_back(b);
if(high[b] == d) continue;
int yi = high[b];
int xi = x[b];
int v = mp[{xi, yi}];
mp[{xi, d}] = n;
high[b] = d;
G[n].push_back({v, d - yi});
G[v].push_back({n, d - yi});
n++;
}
for(int b = 0; b < (int)nv.size() - 1; b++) {
int v1 = mp[{x[nv[b]], d}], v2 = mp[{x[nv[b + 1]], d}];
G[v1].push_back({v2, x[nv[b+1]] - x[nv[b]]});
G[v2].push_back({v1, x[nv[b+1]] - x[nv[b]]});
}
for(int b : rem)
st.erase(b);
}
ll d = dij(s, g, n);
if(d == inf) return -1;
return d;
}
/*
int main() {
int n, m;
assert(2 == scanf("%d%d", &n, &m));
vector<int> x(n), h(n);
for (int i = 0; i < n; i++)
assert(2 == scanf("%d%d", &x[i], &h[i]));
vector<int> l(m), r(m), y(m);
for (int i = 0; i < m; i++)
assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
int s, g;
assert(2 == scanf("%d%d", &s, &g));
fclose(stdin);
long long result = min_distance(x, h, l, r, y, s, g);
printf("%lld\n", result);
fclose(stdout);
return 0;
}
// */
Compilation message
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i = 0; i < l.size(); i++)
| ~~^~~~~~~~~~
walk.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 0; i < skywalks.size(); i++)
| ~~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
49752 KB |
Output is correct |
2 |
Correct |
10 ms |
49756 KB |
Output is correct |
3 |
Correct |
11 ms |
49756 KB |
Output is correct |
4 |
Correct |
10 ms |
49756 KB |
Output is correct |
5 |
Correct |
11 ms |
49756 KB |
Output is correct |
6 |
Correct |
11 ms |
49820 KB |
Output is correct |
7 |
Correct |
11 ms |
49844 KB |
Output is correct |
8 |
Correct |
11 ms |
49752 KB |
Output is correct |
9 |
Correct |
10 ms |
49780 KB |
Output is correct |
10 |
Correct |
11 ms |
50012 KB |
Output is correct |
11 |
Correct |
11 ms |
49756 KB |
Output is correct |
12 |
Correct |
11 ms |
49756 KB |
Output is correct |
13 |
Correct |
11 ms |
49756 KB |
Output is correct |
14 |
Correct |
10 ms |
49756 KB |
Output is correct |
15 |
Correct |
11 ms |
49752 KB |
Output is correct |
16 |
Correct |
10 ms |
49756 KB |
Output is correct |
17 |
Correct |
11 ms |
50012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
49756 KB |
Output is correct |
2 |
Correct |
10 ms |
49752 KB |
Output is correct |
3 |
Correct |
1700 ms |
207952 KB |
Output is correct |
4 |
Correct |
1587 ms |
226196 KB |
Output is correct |
5 |
Correct |
927 ms |
201420 KB |
Output is correct |
6 |
Correct |
822 ms |
181440 KB |
Output is correct |
7 |
Correct |
886 ms |
201396 KB |
Output is correct |
8 |
Correct |
2239 ms |
250544 KB |
Output is correct |
9 |
Correct |
1130 ms |
200392 KB |
Output is correct |
10 |
Correct |
2361 ms |
287916 KB |
Output is correct |
11 |
Correct |
834 ms |
138000 KB |
Output is correct |
12 |
Correct |
554 ms |
117196 KB |
Output is correct |
13 |
Correct |
1959 ms |
261836 KB |
Output is correct |
14 |
Correct |
331 ms |
110676 KB |
Output is correct |
15 |
Correct |
376 ms |
117012 KB |
Output is correct |
16 |
Correct |
355 ms |
117452 KB |
Output is correct |
17 |
Correct |
375 ms |
114888 KB |
Output is correct |
18 |
Correct |
348 ms |
115024 KB |
Output is correct |
19 |
Correct |
22 ms |
52572 KB |
Output is correct |
20 |
Correct |
169 ms |
83816 KB |
Output is correct |
21 |
Correct |
357 ms |
115280 KB |
Output is correct |
22 |
Correct |
355 ms |
115660 KB |
Output is correct |
23 |
Correct |
431 ms |
125616 KB |
Output is correct |
24 |
Correct |
358 ms |
116636 KB |
Output is correct |
25 |
Correct |
379 ms |
116172 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
98 ms |
65980 KB |
Output is correct |
2 |
Runtime error |
3568 ms |
1007576 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
98 ms |
65980 KB |
Output is correct |
2 |
Runtime error |
3568 ms |
1007576 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
49752 KB |
Output is correct |
2 |
Correct |
10 ms |
49756 KB |
Output is correct |
3 |
Correct |
11 ms |
49756 KB |
Output is correct |
4 |
Correct |
10 ms |
49756 KB |
Output is correct |
5 |
Correct |
11 ms |
49756 KB |
Output is correct |
6 |
Correct |
11 ms |
49820 KB |
Output is correct |
7 |
Correct |
11 ms |
49844 KB |
Output is correct |
8 |
Correct |
11 ms |
49752 KB |
Output is correct |
9 |
Correct |
10 ms |
49780 KB |
Output is correct |
10 |
Correct |
11 ms |
50012 KB |
Output is correct |
11 |
Correct |
11 ms |
49756 KB |
Output is correct |
12 |
Correct |
11 ms |
49756 KB |
Output is correct |
13 |
Correct |
11 ms |
49756 KB |
Output is correct |
14 |
Correct |
10 ms |
49756 KB |
Output is correct |
15 |
Correct |
11 ms |
49752 KB |
Output is correct |
16 |
Correct |
10 ms |
49756 KB |
Output is correct |
17 |
Correct |
11 ms |
50012 KB |
Output is correct |
18 |
Correct |
11 ms |
49756 KB |
Output is correct |
19 |
Correct |
10 ms |
49752 KB |
Output is correct |
20 |
Correct |
1700 ms |
207952 KB |
Output is correct |
21 |
Correct |
1587 ms |
226196 KB |
Output is correct |
22 |
Correct |
927 ms |
201420 KB |
Output is correct |
23 |
Correct |
822 ms |
181440 KB |
Output is correct |
24 |
Correct |
886 ms |
201396 KB |
Output is correct |
25 |
Correct |
2239 ms |
250544 KB |
Output is correct |
26 |
Correct |
1130 ms |
200392 KB |
Output is correct |
27 |
Correct |
2361 ms |
287916 KB |
Output is correct |
28 |
Correct |
834 ms |
138000 KB |
Output is correct |
29 |
Correct |
554 ms |
117196 KB |
Output is correct |
30 |
Correct |
1959 ms |
261836 KB |
Output is correct |
31 |
Correct |
331 ms |
110676 KB |
Output is correct |
32 |
Correct |
376 ms |
117012 KB |
Output is correct |
33 |
Correct |
355 ms |
117452 KB |
Output is correct |
34 |
Correct |
375 ms |
114888 KB |
Output is correct |
35 |
Correct |
348 ms |
115024 KB |
Output is correct |
36 |
Correct |
22 ms |
52572 KB |
Output is correct |
37 |
Correct |
169 ms |
83816 KB |
Output is correct |
38 |
Correct |
357 ms |
115280 KB |
Output is correct |
39 |
Correct |
355 ms |
115660 KB |
Output is correct |
40 |
Correct |
431 ms |
125616 KB |
Output is correct |
41 |
Correct |
358 ms |
116636 KB |
Output is correct |
42 |
Correct |
379 ms |
116172 KB |
Output is correct |
43 |
Correct |
98 ms |
65980 KB |
Output is correct |
44 |
Runtime error |
3568 ms |
1007576 KB |
Execution killed with signal 11 |
45 |
Halted |
0 ms |
0 KB |
- |