#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
const int N = 1e5+100;
int n, m;
map<pair<int, int>, int> node;
vector<pair<int,int>> G[N];
vector<int> F[N];
vector<pair<ll, int>> g[N];
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 s, int gg) {
n = x.size();
m = l.size();
for(int i = 0; i < m; ++i){
int u = l[i], v = r[i], L = y[i];
F[u].pb(L);
F[v].pb(L);
G[u].pb({v, L});
G[v].pb({u, L});
}
int co = 0;
for(int i = 0; i < n; ++i){
for(auto U: G[i]){
int u = U.ff; ll w = U.ss;
if(u > i){
int last = i;
for(int j = i; j <= u; ++j){
if(h[j] >= w){
node[{j, w}] = co++;
F[j].pb(w);
}
}
}
}
}
for(int i = 0; i < n; ++i){
F[i].pb(0);
F[i].pb(h[i]);
sort(all(F[i]));
F[i].erase(unique(all(F[i])), F[i].end());
for(int p: F[i]){
// cout << i << ' ' <<p << '\n';
node[{i, p}] = co++;
}
for(int j = 0; j + 1 < F[i].size(); ++j){
// cout << F[i][j] << ' ';
g[node[{i, F[i][j]}]].pb({node[{i, F[i][j + 1]}], F[i][j + 1] - F[i][j]});
g[node[{i, F[i][j + 1]}]].pb({node[{i, F[i][j]}], F[i][j + 1] - F[i][j]});
}
// cout << '\n';
}
// cout << "\n";
for(int i = 0; i < n; ++i){
for(auto U: G[i]){
int u = U.ff; ll w = U.ss;
if(u > i){
int last = i;
for(int j = i; j <= u; ++j){
if(h[j] >= w){
g[node[{last, w}]].pb({node[{j, w}], abs(x[j]-x[last])});
g[node[{j, w}]].pb({node[{last, w}], abs(x[j]-x[last])});
last = j;
}
}
}
}
}
vector<ll> dist(co, INT_MAX);
vector<bool> vis(n);
priority_queue<pair<ll, int>> Q;
Q.push({0, node[{s, 0}]});
dist[node[{s, 0}]] = 0;
while(!Q.empty()){
int v = Q.top().ss; Q.pop();
if(vis[v]) continue;
// cout << v << ' ' << dist[v] << '\n';
vis[v] = 1;
for(auto U: g[v]){
int u = U.ff;
ll w= U.ss;
if(dist[u] > dist[v] + w){
dist[u] = dist[v] + w;;
Q.push({-dist[u], u});
}
}
}
// cout << node[{gg,0}] << ' ';
return dist[node[{gg, 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:32:9: warning: unused variable 'last' [-Wunused-variable]
32 | int last = i;
| ^~~~
walk.cpp:51:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int j = 0; j + 1 < F[i].size(); ++j){
| ~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 2 |
Correct |
1 ms |
7260 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
7516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
7260 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7512 KB |
Output is correct |
| 3 |
Runtime error |
154 ms |
126000 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
31060 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
31060 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 2 |
Correct |
1 ms |
7260 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
7516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
