#include "walk.h"
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
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 from, int to) {
int n = x.size();
int m = l.size();
bool ok = 1;
for(int i = 1; i < n; i++){
ok&=h[i] == h[i-1];
}
if(!ok){
int nodes = n;
matrix<pii> lines;
for(int i = 0; i < n; i++)
lines.push_back({{0,i}});
set<int> s;
vector<int> obuild(n), oline(m);
iota(all(obuild),0);
iota(all(oline),0);
sort(all(obuild),[&](int a, int b){
return h[a] > h[b];
});
sort(all(oline),[&](int a, int b){
return y[a] > y[b];
});
int ptr = 0;
for(int i : oline){
while(ptr < n && h[obuild[ptr]] >= y[i])
s.insert(obuild[ptr]), ptr++;
vector<int> adj;
auto it = s.lower_bound(l[i]);
while(it!=s.end() && *it <= r[i])
adj.push_back(*it), it++;
vector<pii> hor;
for(int i = 0; i < adj.size(); i++){
hor.push_back({x[adj[i]],nodes+i});
}
lines.push_back(hor);
for(int j = 0; j < adj.size(); j++){
//cout << nodes+j << " = " << "(" << x[adj[j]] << ',' << y[i] << ")\n";
lines[adj[j]].push_back({y[i],nodes+j});
}
nodes+=adj.size();
}
matrix<pii> g(nodes);
for(auto& i : lines){
sort(all(i));
for(int j = 1; j < i.size(); j++){
int peso = i[j].ff-i[j-1].ff;
g[i[j-1].ss].push_back({i[j].ss,peso});
g[i[j].ss].push_back({i[j-1].ss,peso});
}
}
vector<ll> dist(nodes,1ll<<60);
dist[from] = 0;
priority_queue<pll,vector<pll>,greater<pll>> pq;
pq.push({0,from});
while(!pq.empty()){
int cur = pq.top().ss;
int curp = pq.top().ff;
pq.pop();
if(curp > dist[cur])
continue;
for(auto [viz,peso] : g[cur]){
if(dist[viz] > dist[cur]+peso){
dist[viz] = dist[cur]+peso;
pq.push({dist[viz],viz});
}
}
}
// for(int i = 0; i < nodes; i++)
// cout << "->" << i << ": " << dist[i] << '\n';
if(dist[to] == (1ll<<60))
return -1;
return dist[to];
}
matrix<pii> g(m+2);
// g[m] -> 0, g[m+1]->n-1
matrix<pii> op(n+1);
for(int i = 0; i < m; i++){
op[l[i]].push_back({1,i});
op[r[i]+1].push_back({0,i});
if(l[i] == 0)
g[m].push_back({i,y[i]}), g[i].push_back({m,y[i]});
if(r[i] == n-1)
g[m+1].push_back({i,y[i]}), g[i].push_back({m+1,y[i]});
}
set<pii> s;
for(int i = 0; i < n; i++){
sort(all(op));
for(auto [type,id]: op[i]){
if(type){
auto it = s.lower_bound({y[id],id});
if(it != s.end()){
g[it->ss].push_back({id,abs(y[id]-it->ff)});
g[id].push_back({it->ss,abs(y[id]-it->ff)});
}
if(it!=s.begin()){
it--;
g[it->ss].push_back({id,abs(y[id]-it->ff)});
g[id].push_back({it->ss,abs(y[id]-it->ff)});
}
s.insert({y[id],id});
} else {
s.erase({y[id],id});
}
}
}
vector<ll> dist(m+2,1ll<<60);
dist[m] = 0;
priority_queue<pll,vector<pll>,greater<pll>> pq;
pq.push({0,m});
while(!pq.empty()){
int cur = pq.top().ss;
int curp = pq.top().ff;
pq.pop();
if(curp > dist[cur])
continue;
for(auto [viz,peso] : g[cur]){
if(dist[viz] > dist[cur]+peso){
dist[viz] = dist[cur]+peso;
pq.push({dist[viz],viz});
}
}
}
// for(int i = 0; i < nodes; i++)
// cout << "->" << i << ": " << dist[i] << '\n';
if(dist[m+1] == (1ll<<60))
return -1;
return dist[m+1]+x.back()-x[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:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = 0; i < adj.size(); i++){
| ~~^~~~~~~~~~~~
walk.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int j = 0; j < adj.size(); j++){
| ~~^~~~~~~~~~~~
walk.cpp:70:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int j = 1; j < i.size(); j++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4070 ms |
8032 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4070 ms |
8032 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
