oj.uz

Submission #703952

# Submission time Handle Problem Language Result Execution time Memory
703952 2023-03-01T05:52:55 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 1620 KB 
/*#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
  
#define fix fixed<<setprecision
#define forn(i, n) for(int i = 1; i <= (n); ++i)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(s) (int) (s).size()
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ss second
#define ff first

using namespace std;
using namespace __gnu_pbds;
using pii = pair<int,int>;
using pll = pair<long long, long long>;
using ll = long long;
using ull = unsigned long long;

 
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 1e5+100, inf = 1e9+7;
int n, q, s[N], e[N], d[N];

void bfs(int lt){
	for(int i = 1; i <= n; ++i)
		d[i] = inf;
	d[lt] = 0;
	queue<int> q;
	q.push(lt);
	while(!q.empty()){
		int i = q.front();
		q.pop();
		for(int j = 1; j <= n; ++j)
			if(j != i && s[j] <= e[i] && e[i] <= e[j] && d[j] == inf){
				d[j] = d[i] + 1;
				q.push(j);
			}
	}
}


int main(){
	//freopen("cownomics.in", "r", stdin);
	//freopen("cownomics.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; ++i)
		cin >> s[i] >> e[i];
	while(q--){
		int a, b;
		cin >> a >> b;
		bfs(a);
		if(d[b] == inf)
			cout << "impossible\n";
		else
			cout << d[b] << '\n';
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 1570 ms 1596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 359 ms 336 KB Output is correct
4 Correct 86 ms 460 KB Output is correct
5 Correct 190 ms 340 KB Output is correct
6 Correct 123 ms 352 KB Output is correct
7 Correct 213 ms 356 KB Output is correct
8 Correct 197 ms 356 KB Output is correct
9 Correct 271 ms 344 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 359 ms 336 KB Output is correct
4 Correct 86 ms 460 KB Output is correct
5 Correct 190 ms 340 KB Output is correct
6 Correct 123 ms 352 KB Output is correct
7 Correct 213 ms 356 KB Output is correct
8 Correct 197 ms 356 KB Output is correct
9 Correct 271 ms 344 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 376 ms 340 KB Output is correct
13 Correct 86 ms 352 KB Output is correct
14 Correct 192 ms 340 KB Output is correct
15 Correct 130 ms 348 KB Output is correct
16 Correct 223 ms 356 KB Output is correct
17 Correct 204 ms 352 KB Output is correct
18 Correct 287 ms 348 KB Output is correct
19 Execution timed out 1580 ms 492 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 359 ms 336 KB Output is correct
4 Correct 86 ms 460 KB Output is correct
5 Correct 190 ms 340 KB Output is correct
6 Correct 123 ms 352 KB Output is correct
7 Correct 213 ms 356 KB Output is correct
8 Correct 197 ms 356 KB Output is correct
9 Correct 271 ms 344 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 324 KB Output is correct
12 Correct 362 ms 352 KB Output is correct
13 Correct 92 ms 352 KB Output is correct
14 Correct 197 ms 340 KB Output is correct
15 Correct 129 ms 344 KB Output is correct
16 Correct 218 ms 372 KB Output is correct
17 Correct 196 ms 356 KB Output is correct
18 Correct 264 ms 352 KB Output is correct
19 Execution timed out 1584 ms 1592 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 1570 ms 1596 KB Time limit exceeded
3 Halted 0 ms 0 KB -