Submission #1193947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193947		uranhishig	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	0 ms	504 KiB

jumps

// #include "jumps.h"
#include <bits/stdc++.h>
#include <cassert>
#include <cstdio>
#include <vector>

using namespace std;


const int mx = 2000;
vector<vector<int>> dst(mx);
vector<vector<int>> adj(mx);


int n;

void init(int N, std::vector<int> H) {
	queue<pair<int, int>> q;
	n = N;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dst[i][j] = INT_MAX;
		}
	}
	
	for (int i = 0; i < n -1 ; i++) {
		for (int j = i + 1; j < n; j++) {
			if(H[j] > H[i]) {
				adj[i].push_back(j);
			}
		}
	}
	
	for (int i = 1; i < n ; i++) {
		for (int j = i - 1; j < n; j++) {
			if(H[j] > H[i]) {
				adj[i].push_back(j);
			}
		}
	}
	
// 	while(!q.empty()) {
// 		q.push({})
// 	}
}



void bfs(int start, int end) {
    queue<pair<int, int>> q;
    vector<bool> vis(4000);
    vis[start] = true;
    q.push({start, 0});
    while (!q.empty()) {
        int X = q.front().first;
        int dist = q.front().second;
        q.pop();
        for(auto Y:adj[X]){
            if(!vis[Y]){
                vis[Y] = 1;
                dst[start][Y] = dst[start][X] + 1;
            }
        }
    }
}
int minimum_jumps(int A, int B, int C, int D) {	
    int sta, end;
	for (int i = A; i <= B; i++) {
		for (int j = C; j <= D; j++) {
			sta = i;
			end = j;
		}
	}
	bfs(sta, end);
	int ans = 1e9;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ans = min(ans, dst[i][j]);
		}
	}
	if(ans==1e9) return -1;
	return ans;
}

• Subtask 1: 0 / 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