Submission #1054376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054376		Gangsta	Rainforest Jumps (APIO21_jumps)	C++14	0 / 100	1 ms	4952 KiB

jumps

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second

using namespace std;
const int N = 2e5 + 1;

int dis[N], n1;

bool sub1 = 0;

vector <int> v[N];

priority_queue <pair<int,int>> pq;

void dij(int x){
	pq.push({0,x});
	dis[x] = 0;
	while(!pq.empty()){
		int a = pq.top().ss;
		pq.pop();
		for(auto i: v[a]){
			if(dis[a] + 1 < dis[i]){
				dis[i] = dis[a] + 1;
				pq.push({-dis[i],i});
			}
		}
	}
}

int minimum_jumps(int a, int b, int c, int d){
	int mn = 1e9;
	for(int i = a; i <= b; i++){
		for(int j = 1; j <= n1; j++) dis[j] = 0;
		dij(i);
		for(int j = c; j <= d; j++) mn = min(mn,dis[j]);
	}
	return mn;
}

void init(int n, vector <int> h){
	n1 = n;
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			if(h[j] > h[i]){
				v[h[i]].pb(h[j]);
				break;
			}
		}
		for(int j = i-1; j >= 0; j--){
			if(h[j] > h[i]){
				v[h[i]].pb(h[j]);
				break;
			}
		}
	}

}


// int main(){
// 	int n, q;
// 	vector <int> v;
// 	cin >> n;
// 	for(int i = 0; i < n; i++){
// 		int x;
// 		cin >> x;
// 		v.pb(x);
// 	}
// 	init(n, v);
// 	cin >> q;
// 	while(q--){
// 		int a, b, c, d;
// 		cin >> a >> b >> c >> d;

// 	}
// }

• 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