Submission #1249030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249030		_rain_	Railway Trip (JOI17_railway_trip)	C++20	20 / 100	101 ms	8136 KiB

railway_trip

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = (int)1e5;
	int a[N+2] , b[N+2] ,l[N+2];
	int n,k,q;

namespace subtask1{
	bool check(){
		return q <= 50;
	}
	
	vector<int>ke[N+2];
		void add_canh(int u,int v){
			ke[u].push_back(v) , ke[v].push_back(u);
			return;
		}
	int d[N+2] = {};
		int bfs(int source,int sink){
			for(int i = 1; i <= n; ++i) d[i] = -1;
			queue<int>q;
			q.push(source);
			d[source] = 0;
			while (q.size()){
				int u = q.front(); q.pop();
				if (u==sink) return d[sink] - 1;
				for(auto&v:ke[u]){
					if (d[v]==-1){
						d[v] = d[u] + 1;
						q.push(v);
					}
				}
			}
			return -1;
		}
	
	void main_code(void){
		vector<int>st;
		for(int i = 1; i <= n; ++i) {
			while (st.size() && l[st.back()] < l[i]) st.pop_back();
			if (st.size()) add_canh(st.back(),i);
			st.push_back(i);
		}
		st.clear();
		for(int i = n; i >= 1; --i) {
			while (st.size() && l[st.back()] < l[i]) st.pop_back();
			if (st.size()) add_canh(st.back(),i);
			st.push_back(i);
		}
		for(int i = 1; i <= q; ++i) cout<<bfs(a[i],b[i])<<'\n';
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
		}
		
		cin>>n>>k>>q;
		for(int i = 1; i <= n; ++i) cin>>l[i];
		for(int i = 1; i <= q; ++i) cin>>a[i]>>b[i];
		if (subtask1::check()) return subtask1::main_code(),0;
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:60:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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