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 "walk.h"
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct node{
long long int dis,id;
}t[10000005];
struct Node{
long long int id,h;
}tmp[3000005],temp[1000005];
int l[1000005],r[1000005],y[1000005],p[10000005],hp[10000005],m,n,road[10000005],map[30000005][3],cntp,pointer[100005],data[30000005][3],num[100005],cont,st,cnt,le[1000005],ri[1000005];
long long int dis[1000005];
int connect(int a,int b,long long int len)
{
//cout<<a<<" "<<b<<" "<<len<<endl;
cont++;
map[cont][0]=b;
map[cont][1]=road[a];
map[cont][2]=len;
road[a]=cont;
cont++;
map[cont][0]=a;
map[cont][1]=road[b];
map[cont][2]=len;
road[b]=cont;
return 0;
}
struct cmp{
bool operator()(const node &a,const node &b)
{
return a.dis>b.dis;
}
};
int dijk()
{
for(int i=1;i<=cnt;i++)dis[i]=100000000000000;
dis[st]=0;
t[1].id=st;
t[1].dis=0;
long long int pp=1;
while(pp>=1)
{
pop_heap(t+1,t+pp+1,cmp());
long long int x=t[pp].id,len=t[pp].dis;
pp--;
if(len!=dis[x])
{
continue;
}
//cout<<x<<" "<<len<<" "<<p[x]<<endl;
long long int g=road[x];
while(g!=-1){
long long int now=map[g][0];
//cout<<now<<" "<<dis[now]<<" "<<p[now]<<" "<<hp[now]<<endl;
if(len+map[g][2]<dis[now]){
dis[now]=len+map[g][2];
pp++;
t[pp].id=now;
t[pp].dis=dis[now];
push_heap(t+1,t+pp+1,cmp());
}
g=map[g][1];
}
//cout<<endl;
}
return 0;
}
bool cmp2(Node a,Node b)
{
return a.h<b.h;
}
int qs(int s,int e)
{
if(s>=e)return 0;
long long int pp=s,qq=e,mid=y[(s+e)/2];
while(pp<=qq)
{
while(y[pp]<mid)pp++;
while(y[qq]>mid)qq--;
if(pp<=qq)
{
swap(l[pp],l[qq]);
swap(r[pp],r[qq]);
swap(y[pp],y[qq]);
pp++;
qq--;
}
}
qs(s,qq);
qs(pp,e);
return 0;
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> lef, std::vector<int> rig, std::vector<int> tmpy, int s, int g) {
n=x.size();
m=lef.size();
for(int i=0;i<m;i++)
{
l[i]=lef[i];
r[i]=rig[i];
y[i]=tmpy[i];
}
qs(0,m-1);
for(int i=0;i<n;i++)
{
temp[i].id=i;
temp[i].h=h[i];
}
for(int i=0;i<=min(10000000,n*m);i++)road[i]=-1;
for(int i=0;i<n;i++)pointer[i]=-1;
sort(temp,temp+n,cmp2);
st=0;
long long int xp=0;
le[0]=-1;
for(int i=1;i<n;i++)
{
le[i]=i-1;
}
ri[n-1]=n;
for(int i=0;i<n-1;i++)
{
ri[i]=i+1;
}
for(int i=0;i<m;i++){
while(y[i]>temp[xp].h)
{
//cout<<xp<<endl;
if(le[temp[xp].id]!=-1)ri[le[temp[xp].id]]=ri[temp[xp].id];
if(ri[temp[xp].id]!=-1)le[ri[temp[xp].id]]=le[temp[xp].id];
xp++;
}
//cout<<i<<" "<<xp<<" "<<y[i]<<" "<<l[i]<<" "<<r[i]<<endl;
cnt++;
num[l[i]]++;
p[cnt]=l[i];
hp[cnt]=y[i];
cntp++;
data[cntp][0]=cnt;
data[cntp][1]=y[i];
data[cntp][2]=pointer[l[i]];
pointer[l[i]]=cntp;
long long int pr=cnt,prex=x[l[i]];
for(int j=ri[l[i]];j<=r[i] && j!=-1 ;j=ri[j]){
//cout<<j<<" ";
cnt++;
cntp++;
data[cntp][0]=cnt;
data[cntp][1]=y[i];
data[cntp][2]=pointer[j];
pointer[j]=cntp;
connect(cnt,pr,x[j]-prex);
pr=cnt;
prex=x[j];
}
//cout<<i<<" "<<m<<endl;
}
cnt++;
st=cnt;
cntp++;
data[cntp][0]=cnt;
data[cntp][1]=0;
data[cntp][2]=pointer[s];
pointer[s]=cntp;
cnt++;
cntp++;
data[cntp][0]=cnt;
data[cntp][1]=0;
data[cntp][2]=pointer[g];
pointer[g]=cntp;
for(int i=0;i<n;i++)
{
long long int g=pointer[i],tmpcount=0;
while(g!=-1)
{
tmpcount++;
tmp[tmpcount].id=data[g][0];
tmp[tmpcount].h=data[g][1];
g=data[g][2];
}
sort(tmp+1,tmp+tmpcount+1,cmp2);
//for(int j=1;j<=tmpcount;j++)cout<<tmp[j].id<<" "<<tmp[j].h<<" ";
//cout<<endl;
for(int j=1;j<tmpcount;j++)
{
connect(tmp[j].id,tmp[j+1].id,tmp[j+1].h-tmp[j].h);
}
//cout<<endl;
}
dijk();
if(dis[cnt]==100000000000000)return -1;
return dis[cnt];
}
# | 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... |