oj.uz

Submission #718989

# Submission time Handle Problem Language Result Execution time Memory
718989 2023-04-05T08:15:24 Z vinnipuh01 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 43120 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define sqrt sqrtl
 
using namespace std;
 
const long long oo = 1e9;
 
int sum, ans = 0, mx = 0, mn = 1000000000, num, pos;
 
 
/*
    ViHHiPuh
 
   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))
 
 
    cout << fixed << setprecision(6) << x;
 
 
    freopen ( "sum.in", "r", stdin )
*/

int n, m, x, y, a[ 100001 ], b[ 100001 ], d[ 100001 ], d1[ 5001 ][ 5001 ];
vector <int> v[ 100001 ];
queue <int> q;

void bfs( int u ) {
	for ( int i = 1; i <= n; i ++ )
		d[ i ] = oo;
	d[ u ] = 0;
	q.push( u );
	while ( q.size() ) {
		int x = q.front();
		q.pop();
		for ( auto to : v[ x ] ) {
			if ( d[ to ] > d[ x ] + 1 ) {
				d[ to ] = d[ x ] + 1;
				q.push( to ); 
			}
		}
	}
}

main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for ( int i = 1; i <= n; i ++ ) {
		cin >> a[ i ] >> b[ i ];
	}
	if ( n <= 5000 ) {
		for ( int i = 1; i <= n; i ++ ) {
			for ( int j = 1; j <= n; j ++ ) {
				if ( a[ j ] <= b[ i ] && b[ i ] <= b[ j ] && i != j ) {
					v[ i ].push_back( j );
				}
			}
		}
		for ( int i = 1; i <= n; i ++ ) {
			bfs( i );
			for ( int j = 1; j <= n; j ++ ) {
				d1[ i ][ j ] = d[ j ];
			}
		}
		while ( m -- ) {
			cin >> x >> y;
			if ( d1[ x ][ y ] == oo )
				cout << "impossible\n";
			else
				cout << d1[ x ][ y ] << "\n";
		}
		return 0;
	}
	else if ( m <= 100 ) {
		for ( int i = 1; i <= n; i ++ ) {
			
		}
		while ( m -- ) {
			cin >> x >> y;
			
		}  
	}
}

Compilation message

events.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | main () {
      | ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 24 ms 5588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 18 ms 10580 KB Output is correct
4 Correct 16 ms 10696 KB Output is correct
5 Correct 20 ms 10624 KB Output is correct
6 Correct 50 ms 11340 KB Output is correct
7 Correct 123 ms 12308 KB Output is correct
8 Correct 142 ms 13268 KB Output is correct
9 Correct 819 ms 14664 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 18 ms 10580 KB Output is correct
4 Correct 16 ms 10696 KB Output is correct
5 Correct 20 ms 10624 KB Output is correct
6 Correct 50 ms 11340 KB Output is correct
7 Correct 123 ms 12308 KB Output is correct
8 Correct 142 ms 13268 KB Output is correct
9 Correct 819 ms 14664 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 19 ms 10592 KB Output is correct
13 Correct 13 ms 10656 KB Output is correct
14 Correct 19 ms 10572 KB Output is correct
15 Correct 45 ms 11404 KB Output is correct
16 Correct 132 ms 12180 KB Output is correct
17 Correct 193 ms 13284 KB Output is correct
18 Correct 743 ms 14652 KB Output is correct
19 Execution timed out 1546 ms 43120 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 18 ms 10580 KB Output is correct
4 Correct 16 ms 10696 KB Output is correct
5 Correct 20 ms 10624 KB Output is correct
6 Correct 50 ms 11340 KB Output is correct
7 Correct 123 ms 12308 KB Output is correct
8 Correct 142 ms 13268 KB Output is correct
9 Correct 819 ms 14664 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2680 KB Output is correct
12 Correct 19 ms 10692 KB Output is correct
13 Correct 14 ms 10580 KB Output is correct
14 Correct 19 ms 10624 KB Output is correct
15 Correct 46 ms 11432 KB Output is correct
16 Correct 121 ms 12260 KB Output is correct
17 Correct 139 ms 13348 KB Output is correct
18 Correct 760 ms 14748 KB Output is correct
19 Incorrect 21 ms 5324 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 3376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 24 ms 5588 KB Output isn't correct
3 Halted 0 ms 0 KB -