oj.uz

Submission #691267

# Submission time Handle Problem Language Result Execution time Memory
691267 2023-01-31T04:09:32 Z amunduzbaev Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 11080 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
//~ #define int ll

const int N = 2e5 + 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;
	vector<int> ss;
	for(int i=0;i<n;i++){
		cin >> a[i];
		while(!ss.empty() && a[ss.back()] < a[i]){
			//~ edges[ss.back()].push_back(i);
			//~ edges[i].push_back(ss.back());
			ss.pop_back();
		}
		if(!ss.empty()){
			edges[ss.back()].push_back(i);
			edges[i].push_back(ss.back());
		}
		ss.push_back(i);
	}
	ss.clear();
	for(int i=n-1;~i;i--){
		while(!ss.empty() && a[ss.back()] < a[i]){
			//~ edges[ss.back()].push_back(i);
			//~ edges[i].push_back(ss.back());
			ss.pop_back();
		}
		if(!ss.empty()){
			edges[ss.back()].push_back(i);
			edges[i].push_back(ss.back());
		}
		ss.push_back(i);
	}
	int d[n];
	while(q--){
		int a, b; cin >> a >> b; a--, b--;
		memset(d, 63, sizeof d);
		queue<int> q;
		q.push(a); d[a] = 0;
		while(!q.empty()){
			int u = q.front(); q.pop();
			for(auto x : edges[u]){
				if(d[x] > d[u] + 1){
					d[x] = d[u] + 1;
					q.push(x);
				}
			}
		}
		
		cout<<--d[b]<<"\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5020 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5024 KB Output is correct
6 Correct 3 ms 5008 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 178 ms 10500 KB Output is correct
3 Correct 169 ms 10528 KB Output is correct
4 Correct 210 ms 10532 KB Output is correct
5 Correct 193 ms 10512 KB Output is correct
6 Correct 182 ms 10760 KB Output is correct
7 Correct 198 ms 10916 KB Output is correct
8 Correct 75 ms 9540 KB Output is correct
9 Correct 75 ms 10440 KB Output is correct
10 Correct 75 ms 10180 KB Output is correct
11 Correct 150 ms 10884 KB Output is correct
12 Correct 145 ms 10972 KB Output is correct
13 Correct 155 ms 10908 KB Output is correct
14 Correct 160 ms 10912 KB Output is correct
15 Correct 152 ms 11080 KB Output is correct
16 Correct 164 ms 10848 KB Output is correct
17 Correct 223 ms 10932 KB Output is correct
18 Correct 186 ms 11044 KB Output is correct
19 Correct 96 ms 10228 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 10268 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 10228 KB Time limit exceeded
2 Halted 0 ms 0 KB -