| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 298695 | eohomegrownapps | Sky Walking (IOI19_walk) | C++14 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<ll,int>> adjlist[10000000]; // weight, node
ll INF = 1e18;
ll dijkstra(int n, int a, int b){
ll distance[10000000]={1e18};
distance[a]=0;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
pq.push({0,a});
while (pq.size()>0){
auto f = pq.top();
pq.pop();
if (f.first>distance[f.second]){continue;}
for (auto p : adjlist[f.second]){
if (distance[f.second]+p.first<distance[p.second]){
distance[p.second]=distance[f.second]+p.first;
pq.push({distance[p.second],p.second});
}
}
}
return (distance[b]==INF)?-1:distance[b];
}
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) {
// x - horizontal distance
int n = x.size();
vector<int> coords = x;
sort(coords.begin(),coords.end());
vector<int> heights(n);
for (int i = 0; i<n; i++){
heights[i]=h[lower_bound(coords.begin(),coords.end(),x[i])-coords.begin()];
}
int m = l.size();
vector<int> inds(m);
for (int i = 0; i<m; i++){
inds[i]=i;
}
sort(inds.begin(),inds.end(),[y](int a, int b){return y[a]<y[b];});
int numnodes = 0;
vector<int> lastnode(n);
vector<int> lastheight(n,0);
//adjlist.resize(n);
for (int i = 0; i<n; i++){
lastnode[i]=i;
}
int curnode = n;
for (int i = 0; i<m; i++){
// process skywalk inds[i]
int lc = l[inds[i]];
int rc = r[inds[i]];
//cout<<"process "<<lc<<' '<<rc<<'\n';
int prev = -1;
for (int j = lc; j<=rc; j++){
//cout<<"heights: "<<heights[j]<<'\n';
// link j to below
if (heights[j]<y[inds[i]]){continue;}
if (lastheight[j]!=y[inds[i]]){
//cout<<"connect "<<curnode<<' '<<lastnode[j]<<'\n';
//adjlist.push_back(vector<pair<ll,int>>());
adjlist[curnode].push_back({y[inds[i]]-lastheight[j],lastnode[j]});
adjlist[lastnode[j]].push_back({y[inds[i]]-lastheight[j],curnode});
lastnode[j]=curnode;
lastheight[j]=y[inds[i]];
curnode++;
}
// link j to left
if (j!=lc){
//cout<<"connect "<<lastnode[j]<<' '<<lastnode[prev]<<'\n';
adjlist[lastnode[j]].push_back({x[j]-x[prev],lastnode[prev]});
adjlist[lastnode[prev]].push_back({x[j]-x[prev],lastnode[j]});
}
prev = j;
}
}
return dijkstra(curnode,s,g);
}