제출 #484145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484145		vinnipuh01	밀림 점프 (APIO21_jumps)	C++17	8 / 100	4059 ms	14256 KiB

jumps

#include "jumps.h"

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

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

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 );
	}
}

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;
}

int minimum_jumps(int A, int B, int C, int D) {
	A ++;
	B ++;
	C ++;
	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;
}

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

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for ( int i = 0 ; i < H.size(); i ++ )
      |                    ~~^~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19