Submission #55048

#	Time	Username	Problem	Language	Result	Execution time	Memory
55048		spencercompton	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	2076 ms	12072 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	int ar[n];
	vector<pair<int, int> > li;
	for(int i = 0; i<n; i++){
		cin >> ar[i];
	}
	int left[n];
	left[0] = 0;
	li.push_back(make_pair(ar[0],0));
	for(int i=  1; i<n; i++){
		while(li[(int)li.size()-1].first<ar[i]){
			li.pop_back();
		}
		left[i] = li[(int)li.size()-1].second;
		li.push_back(make_pair(ar[i],i));
	}
	li.clear();
	int right[n];
	right[n-1] = n-1;
	li.push_back(make_pair(ar[n-1],n-1));
	for(int i = n-2; i>=0; i--){
		while(li[(int)li.size()-1].first<ar[i]){
			li.pop_back();
		}
		right[i] = li[(int)li.size()-1].second;
		li.push_back(make_pair(ar[i],i));
	}
	for(int i = 0; i<q; i++){
		int s, t;
		cin >> s >> t;
		s--;
		t--;
		int dist1[n];
		int dist2[n];
		int inf = n+2;
		for(int j = 0; j<n; j++){
			dist1[j] = inf;
			dist2[j] = inf;
		}
		vector<int> li1;
		dist1[s] = 0;
		li1.push_back(s);
		for(int j = 0; j<li1.size(); j++){
			int now = li1[j];
			if(dist1[left[now]]==inf){
				dist1[left[now]] = dist1[now]+1;
				li1.push_back(left[now]);
			}
			if(dist1[right[now]]==inf){
				dist1[right[now]] = dist1[now]+1;
				li1.push_back(right[now]);
			}
		}
		vector<int> li2;
		dist2[t] = 0;
		li2.push_back(t);
		for(int j = 0; j<li2.size(); j++){
			int now = li2[j];
			if(dist2[left[now]]==inf){
				dist2[left[now]] = dist2[now]+1;
				li2.push_back(left[now]);
			}
			if(dist2[right[now]]==inf){
				dist2[right[now]] = dist2[now]+1;
				li2.push_back(right[now]);
			}
		}
		int ans = inf;
		for(int i = 0; i<n; i++){
			ans = min(ans,dist1[i] + dist2[i] - 1);
		}
		cout << ans << endl;
	}
}

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