Submission #287524

#	Time	Username	Problem	Language	Result	Execution time	Memory
287524		DanerZein	Sky Walking (IOI19_walk)	C++14	0 / 100	4113 ms	707512 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"
#define MAX 100000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vi;
ll dist[1000010];
ll isq[1000010];
vector<vi> G;
void dijktra(ll u){
  memset(isq,0,sizeof isq);
  for(int i=0;i<=1000010;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()){
    int x=pq.top().second;
    int di=pq.top().first;
    pq.pop();
    isq[x]=0;
    if(di>dist[x]) continue;
    for(auto &v:G[x]){
      int 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,int> m;
  for(int i=0;i<x.size();i++){
    no++;
    m[ii(x[i],0)]=no;
    //printf("(%d,%d) %lld\n",x[i],0,no);
  }
  //cout<<endl;
  G.resize(1000000);
  for(int i=0;i<y.size();i++){
    int 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;
	  //printf("(%d,%d) %lld\n",x[j],y[i],no);
	}
	if(ant==-1){
	  ant=m[ii(x[j],y[i])];
	  id=j;
	}
	else{
	  int dis=abs(x[j]-x[id]);
	  int 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;
      }
      }
    }
  }
  for(int i=0;i<x.size();i++){
    int ant=0;
    for(int j=1;j<=h[i];j++){
      if(m[ii(x[i],j)]!=0){
	int u=m[ii(x[i],j)];
	int v=m[ii(x[i],ant)];
	int w=abs(ant-j);
	G[u].push_back(ii(w,v));
	G[v].push_back(ii(w,u));
	ant=j;
      }
    }
  }
  /*for(int i=0;i<26;i++){
    cout<<i<<" : ";
    for(int j=0;j<G[i].size();j++){
      cout<<"("<<G[i][j].second<<", "<<G[i][j].first<<") ";
    }
    cout<<endl;
  }*/
  dijktra(m[ii(x[s],0)]);
  return dist[m[ii(x[g],0)]];
}

Compilation message (stderr)

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:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i=0;i<x.size();i++){
      |               ~^~~~~~~~~
walk.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i=0;i<y.size();i++){
      |               ~^~~~~~~~~
walk.cpp:73:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(int i=0;i<x.size();i++){
      |               ~^~~~~~~~~
walk.cpp: In function 'void dijktra(ll)':
walk.cpp:14:12: warning: iteration 1000010 invokes undefined behavior [-Waggressive-loop-optimizations]
   14 |     dist[i]=MAX;
      |            ^
walk.cpp:13:16: note: within this loop
   13 |   for(int i=0;i<=1000010;i++){
      |               ~^~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43