This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
const int nax=2e6;
vector<pair<int,int>> adj[nax];
vector<long long> dis(nax);
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 g) {
int n=x.size();
int k=l.size();
int cnt=n;
vector<pair<int,pair<int,int>>> tab(k);
for (int i = 0; i < k; ++i)
{
tab[i]={y[i],{l[i],r[i]}};
}
sort(tab.begin(),tab.end());
map<int,pair<int,int>> mp;
for (int i = 0; i < n; ++i)
{
mp[x[i]]={i,0};
}
for (int i = 0; i < k; ++i)
{
for (int j = tab[i].se.fi; j <= tab[i].se.se; ++j)
{
if(tab[i].fi<=h[j]){
adj[cnt].pb({mp[x[j]].fi,tab[i].fi-mp[x[j]].se});
adj[mp[x[j]].fi].pb({cnt,tab[i].fi-mp[x[j]].se});
mp[x[j]]={cnt,tab[i].fi};
}
if(j>tab[i].se.fi){
adj[cnt].pb({cnt-1,x[j]-x[j-1]});
adj[cnt-1].pb({cnt,x[j]-x[j-1]});
}
cnt++;
}
}
for (int i = 0; i < cnt; ++i)
{
dis[i]=1e18;
}
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
pq.push({0,s});
dis[s]=0;
//cout <<"hey"<<endl;
//int t=5;
while(!pq.empty()){
//cout <<t<<endl;
//if(t==0) break;
//t--;
ll d=pq.top().fi;
ll x=pq.top().se;
//cout <<x<<" "<<d<<endl;
pq.pop();
if(x==g){
return d;
}
if(dis[x]!=d) continue;
for(auto u:adj[x]){
//cout <<"n "<<u.fi<<endl;
ll newd=u.se+d;
//cout <<u.se<<endl;
if(newd>=dis[u.fi]) continue;
dis[u.fi]=newd;
pq.push({newd,u.fi});
}
}
return -1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |