Submission #287421

#	Time	Username	Problem	Language	Result	Execution time	Memory
287421		DanerZein	Sky Walking (IOI19_walk)	C++14	0 / 100	4124 ms	691408 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"
#define MAX 100000000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
ll dist[10000100];
ll isq[10000100];
vector<vi> G;
void bfs(ll u){
  memset(isq,0,sizeof isq);
  memset(dist,-1,sizeof dist);
  queue<ll> q;
  q.push(u);
  dist[u]=0;
  isq[u]=1;
  while(!q.empty()){
    ll x=q.front();
    isq[x]=0;
    q.pop();
    for(auto &v: G[x]){
      if(dist[v]>dist[x]+1 or dist[v]==-1){
	dist[v]=dist[x]+1;
	if(isq[v]==0){
	  q.push(v);
	  isq[v]=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(10000000);
  for(int i=0;i<x.size();i++){
    for(int j=0;j<=h[i];j++){
      if(m[ii(x[i],j)]==0){
	no++;
	m[ii(x[i],j)]=no;
      }
      if(j!=0){
	ll v=m[ii(x[i],j-1)];
	ll u=m[ii(x[i],j)];
	G[v].push_back(u);
	G[u].push_back(v);
      }
    }
  }
  for(int i=0;i<y.size();i++){
    for(int j=x[l[i]];j<=x[r[i]];j++){
      if(m[ii(j,y[i])]==0){
	no++;
	m[ii(j,y[i])]=no;
      }
      if(j!=x[l[i]]){
	ll u=m[ii(j-1,y[i])];
	ll v=m[ii(j,y[i])];
	G[u].push_back(v);
	G[v].push_back(u);
      }
    }
  }
  bfs(m[ii(x[s],0)]);
  // cout<<m[ii(x[s],0)]<<" "<<m[ii(x[g],0)]<<endl;
  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:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int i=0;i<x.size();i++){
      |               ~^~~~~~~~~
walk.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0;i<y.size();i++){
      |               ~^~~~~~~~~

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