Submission #287532

#	Time	Username	Problem	Language	Result	Execution time	Memory
287532		DanerZein	Sky Walking (IOI19_walk)	C++14	0 / 100	55 ms	6904 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[3000];
ll isq[3000];
vector<vi> G;
void dijktra(ll u){
  memset(isq,0,sizeof isq);
  for(int i=0;i<=3000;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;
  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(3010);
  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;
	  //printf("(%d,%d) %lld\n",x[j],y[i],no);
	}
	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;
      }
      }
    }
  }
  for(int i=0;i<x.size();i++){
    ll ant=0;
    for(int j=1;j<=h[i];j++){
      if(m[ii(x[i],j)]!=0){
	ll u=m[ii(x[i],j)];
	ll v=m[ii(x[i],ant)];
	ll w=abs(ant-j);
	G[u].push_back(ii(w,v));
	G[v].push_back(ii(w,u));
	ant=j;
      }
    }
  }
  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;
}

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 3000 invokes undefined behavior [-Waggressive-loop-optimizations]
   14 |     dist[i]=MAX;
      |            ^
walk.cpp:13:16: note: within this loop
   13 |   for(int i=0;i<=3000;i++){
      |               ~^~~~~~

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