Submission #484146

#	Time	Username	Problem	Language	Result	Execution time	Memory
484146		vinnipuh01	Rainforest Jumps (APIO21_jumps)	C++17	Compilation error	0 ms	0 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>
#include <vector>

using namespace std;
int n;
int a[ 200001 ];
vector <int> v[ 200001 ], vv;

bool ok;

void init(int N, vector<int> H) {
	n = N;
	for ( int i = 0 ; i < H.size(); i ++ )
		a[ i + 1 ] = H[ i ];
	for ( int i = 1; i <= n; i ++ ) {
		while ( vv.size() && a[ vv.back() ] < a[ i ] ) {
			vv.pop_back();
		}
		if ( vv.size() ) {
			v[ i ].push_back( vv.back() );
		}
		vv.push_back( i );
	}
	vv.clear();
	for ( int i = n; i >= 1; i -- ) {
		while ( vv.size() && a[ vv.back() ] < a[ i ] ) {
			vv.pop_back();
		}
		if ( vv.size() )
			v[ i ].push_back( vv.back() );
		vv.push_back( i );
	}
	for ( int i = n; i > 1; i -- ) {
		if ( a[ i ] <= a[ i - 1 ] )
			ok = 1;
	}
}

const long long oo = 1e18;
long long mx, mn;
int c, f;
long long int d[ 200001 ];
queue <int> q;

long long int bfs( int u ) {
	for ( int i = 1; i <= n; i ++ )
		d[ i ] = oo;
	d[ u ] = 0;
	q.push( u );
	while ( q.size() ) {
		int g = q.front();
		q.pop();
		for ( auto to : v[ g ] ) {
			if ( d[ to ] > d[ g ] + 1 ) {
				d[ to ] = d[ g ] + 1;
				q.push( to );
			}
		}
	}
	mx = oo;
	for ( int i = c; i <= f; i ++ ) {
		mx = min( mx, d[ i ] );
	}
	return mx;
}

long long int minimum_jumps(int A, int B, int C, int D) {
	A ++;
	B ++;
	C ++;
	D ++;
	if ( !ok ) {
		if ( C > B )
			return C - B;
		else
			return A - D;
	}
	c = C;
	f = D;
	mn = oo;
	for ( int i = A; i <= B; i ++ ) {
		mn = min( mn, bfs( i ) + 0ll );
	}
	if ( mn == oo )
		return -1;
  return mn;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for ( int i = 0 ; i < H.size(); i ++ )
      |                    ~~^~~~~~~~~~
jumps.cpp: At global scope:
jumps.cpp:69:15: error: ambiguating new declaration of 'long long int minimum_jumps(int, int, int, int)'
   69 | long long int minimum_jumps(int A, int B, int C, int D) {
      |               ^~~~~~~~~~~~~
In file included from jumps.cpp:1:
jumps.h:4:5: note: old declaration 'int minimum_jumps(int, int, int, int)'
    4 | int minimum_jumps(int A, int B, int C, int D);
      |     ^~~~~~~~~~~~~