Submission #570094

#	Time	Username	Problem	Language	Result	Execution time	Memory
570094		Cyber_Wolf	Rainforest Jumps (APIO21_jumps)	C++14	4 / 100	4086 ms	9780 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;
	vector<lg> loc(N+1);
	for(int i = 0; i < N; i++)
	{
		loc[H[i]] = i;
	}
	set<lg> se;
	se.emplace(loc[N]);
	for(int i = N-1; i >= 1; i--)
	{
		lg mnm = LLONG_MAX;
		for(auto it : se)
		{
			if(abs(mnm-loc[i]) > abs(loc[i]-it))
			{
				mnm = it;
			}
			else	break;
		}
		adj[loc[i]].push_back(mnm);
		se.emplace(loc[i]);
	}
}
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: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19