oj.uz

Submission #889211

# Submission time Handle Problem Language Result Execution time Memory
889211 2023-12-19T07:59:25 Z Cutebol Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 17328 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

bool YES(bool f){ if(f) cout << "Yes\n" ; else cout << "No\n" ; return f ; }
void YES(){cout << "Yes\n" ;}
void NO(){cout << "No\n" ;}
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define ld long double
#define pii pair <int , int>
#define ff first
#define ss second
#define endl '\n'

const int N = 3e5 + 5 ;
const int inf = 1e18 ;
const int mod = 998244353 ;
const double eps = 1e-8 ;

int binpow( int a , int b ){
  if ( b == 0 ) return 1 ;
  int x = binpow ( a , b/2 ) ;
  if ( !(b%2) ) return (x*x) ;
  return (x*x*a) ;
}
template <class T>
bool chmax( T& x , const T& y ){
  bool f = 0 ;
  if ( x < y ) x = y , f = 1 ;
  return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
  bool f = 0 ;
  if ( x > y ) x = y , f = 1 ;
  return f ;
}

//code

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

int bfs ( int s , int x ){
	for ( int i = 0 ; i <= n ; i ++ ) d[i] = inf ;
	d[s] = 0 ;
	queue <int> q ;
	q.push(s) ;
	while (!q.empty()){
		int v = q.front() ;
		//cout << v << endl ;
		q.pop() ;
		for ( auto to : g[v] ){
			if ( chmin (d[to] , d[v] + 1 )) q.push(to) ;
		}
	}
	return d[x]-1 ;
}

void solve(){
	
	cin >> n >> k >> q ;
	for ( int i = 1 ; i <= n ; i ++  ) cin >> a[i] ;
	for ( int i = 1 ; i < n ; i ++ ){
		int mn = 0 ;
		for ( int j = i+1 ; j <= n ; j ++ ){
			if ( chmax ( mn , a[j]) ){
				g[i].push_back(j) ;
				g[j].push_back(i) ;
			}
			if ( mn >= a[i] ) break ;
		}
	}
	while ( q -- ){
		int x , y ; cin >> x >> y ;
		cout << bfs(x,y) << endl ;
	}
	
	
}

signed main(){
    ios ;
	int t = 1 ;
	//cin >> t ;
	while ( t -- ) solve() ;
}

Compilation message

railway_trip.cpp: In function 'void fopn(std::string)':
railway_trip.cpp:10:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:10:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 115 ms 15708 KB Output is correct
3 Correct 117 ms 15964 KB Output is correct
4 Correct 122 ms 16444 KB Output is correct
5 Correct 122 ms 16548 KB Output is correct
6 Correct 128 ms 16788 KB Output is correct
7 Correct 130 ms 16976 KB Output is correct
8 Correct 35 ms 14172 KB Output is correct
9 Correct 1986 ms 15312 KB Output is correct
10 Correct 1753 ms 14508 KB Output is correct
11 Correct 897 ms 15696 KB Output is correct
12 Correct 416 ms 15596 KB Output is correct
13 Correct 380 ms 15516 KB Output is correct
14 Correct 823 ms 15904 KB Output is correct
15 Correct 891 ms 15696 KB Output is correct
16 Correct 693 ms 15604 KB Output is correct
17 Correct 128 ms 17156 KB Output is correct
18 Correct 128 ms 17152 KB Output is correct
19 Correct 75 ms 17232 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2047 ms 16208 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 2045 ms 17328 KB Time limit exceeded
2 Halted 0 ms 0 KB -