제출 #287548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
287548		DanerZein	Sky Walking (IOI19_walk)	C++14	10 / 100	50 ms	6264 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"
#define MAX 1000000000000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vi;
ll dist[2600];
ll isq[2600];
vector<vi> G;
void dijktra(ll u){
  memset(isq,0,sizeof isq);
  for(int i=0;i<=2600;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(2600);
  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;
}

컴파일 시 표준 에러 (stderr) 메시지

walk.cpp: In function 'void dijktra(ll)':
walk.cpp:22:8: warning: unused variable 'di' [-Wunused-variable]
   22 |     ll di=pq.top().first;
      |        ^~
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:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i=0;i<y.size();i++){
      |               ~^~~~~~~~~
walk.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int i=1;i<aux.size();i++){
      |               ~^~~~~~~~~~~
walk.cpp: In function 'void dijktra(ll)':
walk.cpp:14:12: warning: iteration 2600 invokes undefined behavior [-Waggressive-loop-optimizations]
   14 |     dist[i]=MAX;
      |            ^
walk.cpp:13:16: note: within this loop
   13 |   for(int i=0;i<=2600;i++){
      |               ~^~~~~~
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:58:24: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |    ll dis=abs(x[j]-x[id]);
      |                        ^

• 서브태스크 1: 10 / 10
• 서브태스크 2: 0 / 14
• 서브태스크 3: 0 / 15
• 서브태스크 4: 0 / 18
• 서브태스크 5: 0 / 43