Submission #570077

#	Time	Username	Problem	Language	Result	Execution time	Memory
570077		Cyber_Wolf	Rainforest Jumps (APIO21_jumps)	C++14	25 / 100	4043 ms	15108 KiB

jumps

#include "jumps.h"
//#include "stub.cpp"
#include <bits/stdc++.h>

using namespace std;

#define lg long long

const lg sz = 2e5+5;

vector<lg> adj[sz];
bool flag = true;

void init(int N, std::vector<int> H) 
{
	for(int i = 0; i < N; i++)	
		flag &= (H[i] == i+1);
	if(flag)	return;
	for(int i = 0; i < N; i++)
	{
		lg idx = i-1;
		while(idx >= 0)
		{
			if(H[idx] > H[i])
			{
				adj[i].push_back(idx);
				break;
			}
			idx--;
		}
		idx = i+1;
		while(idx < N)
		{
			if(H[idx] > H[i])
			{
				adj[i].push_back(idx);
				break;
			}
			idx++;
		}
	}
}
lg vis[sz], tmp;

int minimum_jumps(int A, int B, int C, int D)
{
	if(flag)
	{
		return C-B;
	}
	tmp++;
	lg ans = -1;
	queue<lg> q;
	for(int i = A; i <= B; i++)	q.push(i), vis[i] = true;
	lg dist = 0;
	while(q.size() && ans == -1)
	{
		lg sz = q.size();
		dist++;
		while(sz-- && ans == -1)
		{
			lg u = q.front();
			q.pop();
			for(auto it : adj[u])
			{
				if(vis[it] == tmp)	continue;
				if(it >= C && it <= D)
				{
					ans = dist;
					break;
				}
				vis[it] = tmp;
				q.push(it);
			}
		}
	}
	
	return ans;
}

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