oj.uz

Submission #287548

# Submission time Handle Problem Language Result Execution time Memory
287548 2020-08-31T19:54:28 Z DanerZein Sky Walking (IOI19_walk) C++14
10 / 100
 50 ms 6264 KB 
#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;
}

Compilation message

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]);
      |                        ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 540 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 640 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 50 ms 6264 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 3756 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 3756 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 540 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 640 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Runtime error 50 ms 6264 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -