Submission #563183

#	Time	Username	Problem	Language	Result	Execution time	Memory
563183		amunduzbaev	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	2068 ms	10736 KiB

railway_trip

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long

const int N = 1e5 + 5;
vector<int> edges[N];
int a[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k, q; cin>>n>>k>>q;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	
	vector<int> st;
	for(int i=0;i<n;i++){
		bool is = 0;
		while(!st.empty() && a[st.back()] <= a[i]){
			is |= (a[st.back()] == a[i]);
			edges[i].push_back(st.back());
			edges[st.back()].push_back(i);
			st.pop_back();
		}
		
		if(!is && !st.empty()){
			edges[i].push_back(st.back());
			edges[st.back()].push_back(i);
		}
		
		st.push_back(i);
	}
	
	auto bfs = [&](int a, int b){
		queue<int> qq;
		vector<int> d(n, n);
		d[a] = 0; qq.push(a);
		while(!qq.empty()){
			int u = qq.front(); qq.pop();
			for(auto x : edges[u]){
				if(d[x] > d[u] + 1){
					d[x] = d[u] + 1;
					qq.push(x);
				}
			}
		}
		
		return d[b] - 1;
	};
	
	while(q--){
		int a, b; cin>>a>>b;
		a--, b--;
		cout<<bfs(a, b)<<"\n";
	}
}
 

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55