Submission #727221

#	Time	Username	Problem	Language	Result	Execution time	Memory
727221		iskhakkutbilim	Rainforest Jumps (APIO21_jumps)	C++14	37 / 100	4029 ms	22536 KiB

jumps

//#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
int dis[2001][2001];
vector<int> g[MAXN+1], Dis(MAXN+1), used(MAXN+1);
vector<int> h;
int n, srt, timer = 1;
queue<int> q;
void init(int N, vector<int> H){	
	n = N, srt = 1, h = H;
	for(int i = 1;i < N; i++){
		if(h[i-1] > h[i]) srt = 0;
	}
	stack<int> st;
	st.push(MAXN+MAXN);
	for(int i = N-1;i >= 0; i--){
		while(h[i] >= st.top()){
			st.pop();
		}
		if(st.top()<= MAXN) g[h[i]].push_back(st.top());
		st.push(h[i]);
	}
	reverse(h.begin(), h.end());
	while(!st.empty()) st.pop();
	st.push(MAXN+MAXN);
	for(int i = N-1;i >= 0; i--){
		while(h[i] >= st.top()){
			st.pop();
		}
		if(st.top()<= MAXN) g[h[i]].push_back(st.top());
		st.push(h[i]);
	}
	reverse(h.begin(), h.end());
	if(srt) return;
	if(n > 2000)  return;
	memset(dis, -1, sizeof(dis));
	
	for(int i = 1;i <= n; i++){
		q.push(i);
		dis[i][i] = 0;
		while(!q.empty()){
			int v = q.front(); q.pop();
			for(int to : g[v]){
				if(dis[i][to] == -1){
					dis[i][to] = dis[i][v]+1;
					q.push(to);
				}
			}
		}
	}
}

int minimum_jumps(int A, int B, int C, int D){
	timer++;
	if(srt){
		return C-B;
	}
	if(A==B and C == D){
		if(h[A] > h[C]) return -1;
		q.push(h[A]);
		Dis[h[A]] = 0;
		used[h[A]] = timer;
		while(!q.empty()){
			int v = q.front(); q.pop();
			if(v==h[C]) break;
			if(v > h[C]) continue;
			for(int to : g[v]){
				if(used[to] != timer){
					used[to] = timer;
					Dis[to] = Dis[v]+1;
					q.push(to);
				}
			}
		}
		while(!q.empty()) q.pop();
		if(used[h[C]] != timer) return -1;
		return Dis[h[C]];
	}
	int mn = INT_MAX;
	if(n <= 2000){
		for(int i = A; i <= B; i++){
			for(int j = C; j <= D; j++){
				if(dis[h[i]][h[j]] != -1) mn = min(mn, dis[h[i]][h[j]]);
			}
		}
	}else{
		vector<int> dist(n+1, -1);
		
		for(int i = A;i <= B;i++){
			q.push(h[i]);
			dist[h[i]] = 0;
		}
		while(!q.empty()){
			int v = q.front(); q.pop();
			for(int to : g[v]){
				if(dist[to] == -1){
					dist[to] = dist[v]+1;
					q.push(to);
				}
			}
		}
		for(int i = C; i <= D; i++) if(dist[h[i]] != -1) mn= min(mn, dist[h[i]]);
	}
	if(mn == INT_MAX) mn = -1;
	return mn;
}


//main(){
//	int N; cin >> N;
//	vector<int> H(N);
//	for(int i = 0;i < N; i++) cin >> H[i];
//	init(N, H);
//	cout << minimum_jumps(4, 4, 6, 6) << '\n';
//	cout << minimum_jumps(1, 3, 5, 6) << '\n';
//	cout << minimum_jumps(0, 1, 2, 2) << '\n';
//	
//}

• 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