oj.uz

Submission #889214

# Submission time Handle Problem Language Result Execution time Memory
889214 2023-12-19T08:02:16 Z Minbaev Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 17356 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define f first
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
const int mod= 1e9 +7;
const int N=1e5*4;

int binpow (int a, int n) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return binpow (a, n-1) * a;
	else {
		int b = binpow (a, n/2);
		return b * b;
	}
}

vector<int>g[N];
	int n,m,k,q;

void bfs(int x,int y){
	vector<int>dist(n+1,mod);
	dist[x] = 0;
	queue<int>q;
	q.push(x);
	while(!q.empty()){
		auto ind = q.front();
		q.pop();
		
		for(auto to:g[ind]){
			if(umin(dist[to],dist[ind] + 1)){
				q.push(to);
			}
		}
		
	}
	cout<<dist[y] - 1<<"\n";	
	
}

void solve(){

	cin>>n>>m>>q;
	
	vector<int>a(n+1);
	for(int i = 1;i<=n;i++){
		cin>>a[i];
	}
	
	for(int i = 0 ; i <= n;i++){
		int mx = 0;
		for(int j = i + 1;j<=n;j++){
			if(umax(mx,a[j])){
				g[i].pb(j);
				g[j].pb(i);	
			}
			if(mx>=a[i])break;
		}
	}
	while(q--){
		int x,y;
		cin>>x>>y;
		bfs(x,y);
	}









}

 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int cnt=0;
	int tt=1;//cin>>tt;
	while(tt--)solve();

}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 119 ms 16232 KB Output is correct
3 Correct 123 ms 16476 KB Output is correct
4 Correct 117 ms 16732 KB Output is correct
5 Correct 134 ms 16728 KB Output is correct
6 Correct 124 ms 16732 KB Output is correct
7 Correct 136 ms 16984 KB Output is correct
8 Correct 41 ms 14492 KB Output is correct
9 Correct 1741 ms 14908 KB Output is correct
10 Correct 1337 ms 14820 KB Output is correct
11 Correct 983 ms 15544 KB Output is correct
12 Correct 928 ms 15564 KB Output is correct
13 Correct 831 ms 15608 KB Output is correct
14 Correct 843 ms 15348 KB Output is correct
15 Correct 821 ms 15440 KB Output is correct
16 Correct 829 ms 15492 KB Output is correct
17 Correct 138 ms 17092 KB Output is correct
18 Correct 122 ms 16988 KB Output is correct
19 Correct 80 ms 17240 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2031 ms 16376 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 2049 ms 17356 KB Time limit exceeded
2 Halted 0 ms 0 KB -