Submission #570109

#	Time	Username	Problem	Language	Result	Execution time	Memory
570109		Cyber_Wolf	Rainforest Jumps (APIO21_jumps)	C++14	37 / 100	4022 ms	24612 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) 
{
	vector<lg> loc(N+1);
	for(int i = 0; i < N; i++)
	{
		flag &= (H[i] == i+1);
		loc[H[i]] = i;
	}
	if(flag)	return;
	set<lg> se;
	se.emplace(loc[N]);
	for(int i = N-1; i >= 1; i--)
	{
		auto it = se.lower_bound(loc[i]);
		if(it != se.end())	adj[loc[i]].push_back(*it);
		if(it != se.begin())	adj[loc[i]].push_back(*(--it));
		se.emplace(loc[i]);
	}
	/*
	for(int i = 0; i < N; i++)
	{
		for(auto it : adj[i])
		{
			cout << it << ' ';
		}
		cout << '\n';
	}*/
}
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: 12 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19