| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 287561 | DanerZein | 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 <bits/stdc++.h>
#include "walk.h"
#define msize 2500000
#define MAX 9223372036854775806
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vi;
ll dist[msize];
ll isq[msize];
vector<vi> G;
void dijktra(ll u){
memset(isq,0,sizeof isq);
for(int i=0;i<=msize;i++){
dist[i]=MAX;
}
priority_queue<ii,vi,greater<ii> > pq;
dist[u]=0;
isq[u]=1;
pq.push(ii(0,u));
while(!pq.empty()){
ll x=pq.top().second;
ll di=pq.top().first;
pq.pop();
isq[x]=0;
// if(di>dist[x]) continue;
for(auto &v:G[x]){
ll w=v.first;
if(dist[v.second]>dist[x]+w){
dist[v.second]=dist[x]+w;
if(isq[v.second]==0){
pq.push(ii(dist[v.second],v.second));
isq[v.second]=1;
}
}
}
}
}
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) {
ll no;
no=0;
map<ii,ll> m;
G.resize(msize);
vi aux;
for(int i=0;i<y.size();i++){
ll ant=-1,id;
for(int j=l[i];j<=r[i];j++){
if(h[j]>=y[i]){
if(m[ii(x[j],y[i])]==0){
no++;
m[ii(x[j],y[i])]=no;
}
aux.push_back(ii(x[j],y[i]));
if(ant==-1){
ant=m[ii(x[j],y[i])];
id=j;
}
else{
ll dis=abs(x[j]-x[id]);
ll u=m[ii(x[j],y[i])];
G[ant].push_back(ii(dis,u));
G[u].push_back(ii(dis,ant));
ant=u;
id=j;
}
}
}
}
if(m[ii(x[s],0)]==0){
no++;
m[ii(x[s],0)]=no;
aux.push_back(ii(x[s],0));
}
if(m[ii(x[g],0)]==0){
no++;
m[ii(x[g],0)]=no;
aux.push_back(ii(x[g],0));
}
sort(aux.begin(),aux.end());
for(int i=1;i<aux.size();i++){
if(aux[i].first==aux[i-1].first){
int u=m[ii(aux[i].first,aux[i].second)];
int v=m[ii(aux[i-1].first,aux[i-1].second)];
int w=abs(aux[i].second-aux[i-1].second);
G[u].push_back(ii(w,v));
G[v].push_back(ii(w,u));
}
}
dijktra(m[ii(x[s],0)]);
if(dist[m[ii(x[g],0)]]==MAX) dist[m[ii(x[g],0)]]=-1;
ll res=dist[m[ii(x[g],0)]];
return res;
}
#include <bits/stdc++.h>
#include "walk.h"
#define msize 2500000
#define MAX 9223372036854775806
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vi;
ll dist[msize];
ll isq[msize];
vector<vi> G;
void dijktra(ll u){
memset(isq,0,sizeof isq);
for(int i=0;i<=msize;i++){
dist[i]=MAX;
}
priority_queue<ii,vi,greater<ii> > pq;
dist[u]=0;
isq[u]=1;
pq.push(ii(0,u));
while(!pq.empty()){
ll x=pq.top().second;
ll di=pq.top().first;
pq.pop();
isq[x]=0;
// if(di>dist[x]) continue;
for(auto &v:G[x]){
ll w=v.first;
if(dist[v.second]>dist[x]+w){
dist[v.second]=dist[x]+w;
if(isq[v.second]==0){
pq.push(ii(dist[v.second],v.second));
isq[v.second]=1;
}
}
}
}
}
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) {
ll no;
no=0;
map<ii,ll> m;
G.resize(msize);
vi aux;
for(int i=0;i<y.size();i++){
ll ant=-1,id;
for(int j=l[i];j<=r[i];j++){
if(h[j]>=y[i]){
if(m[ii(x[j],y[i])]==0){
no++;
m[ii(x[j],y[i])]=no;
}
aux.push_back(ii(x[j],y[i]));
if(ant==-1){
ant=m[ii(x[j],y[i])];
id=j;
}
else{
ll dis=abs(x[j]-x[id]);
ll u=m[ii(x[j],y[i])];
G[ant].push_back(ii(dis,u));
G[u].push_back(ii(dis,ant));
ant=u;
id=j;
}
}
}
}
if(m[ii(x[s],0)]==0){
no++;
m[ii(x[s],0)]=no;
aux.push_back(ii(x[s],0));
}
if(m[ii(x[g],0)]==0){
no++;
m[ii(x[g],0)]=no;
aux.push_back(ii(x[g],0));
}
sort(aux.begin(),aux.end());
for(int i=1;i<aux.size();i++){
if(aux[i].first==aux[i-1].first){
int u=m[ii(aux[i].first,aux[i].second)];
int v=m[ii(aux[i-1].first,aux[i-1].second)];
int w=abs(aux[i].second-aux[i-1].second);
G[u].push_back(ii(w,v));
G[v].push_back(ii(w,u));
}
}
dijktra(m[ii(x[s],0)]);
if(dist[m[ii(x[g],0)]]==MAX) dist[m[ii(x[g],0)]]=-1;
ll res=dist[m[ii(x[g],0)]];
return res;
}