Submission #1193949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193949		uranhishig	Rainforest Jumps (APIO21_jumps)	C++20	8 / 100	4064 ms	17396 KiB

jumps

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

using namespace std;


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


int n;

void init(int N=7, std::vector<int> H={3, 2, 1, 6, 4, 5, 7}) {
	queue<pair<int, int>> q;
	n = N;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
		    if(i==j) continue;
			dst[i][j] = 1e9;
		}
	}

	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);
				break;
			}
		}
	}
	
	for (int i = 1; i < n ; i++) {
		for (int j = i - 1; j>=0; j--) {
			if(H[j] > H[i]) {
				adj[i].push_back(j);
				break;
			}
		}
	}
}

void bfs(int start) {
    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;
                q.push({Y,dst[start][Y]});
            }
        }
    }
}
int minimum_jumps(int A, int B, int C, int D) {	
    int sta, end;
	for (int i = A; i <= B; i++) {
	    bfs(i);
	}
	int ans = 1e9;
	for (int i = A; i <=B; i++) {
		for (int j = C; j <=D; j++) {
			ans = min(ans, dst[i][j]);
		}
	}
	if(ans==1e9) return -1;
	return ans;
}

• 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