oj.uz

Submission #701329

# Submission time Handle Problem Language Result Execution time Memory
701329 2023-02-20T23:16:14 Z angelo_torres Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 40952 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = 5e3 + 10;

int n,q,s[N],e[N],d[N][N];
bool o[N];
vector<int> g[N];

void bfs(int v){
	for(int i = 1; i <= n; ++i) d[v][i] = N, o[i] = 0;
	d[v][v] = 0;
	queue<int> q;
	q.push(v);
	while(!q.empty()){
		int r = q.front();
		q.pop();
		for(auto u : g[r]){
			if(!o[u]){
				o[u] = 1, d[v][u] = d[v][r]+1;
				q.push(u);
			} 
		}
	}
}

int main(){
	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];
	if(n <= 5000){
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j <= n; ++j){
				if(i == j) continue;
				if(s[j] <= e[i] && e[i] <= e[j]){
					// cout << i << " " << j << "\n";
					g[i].push_back(j);
				}
			}
		}
		for(int i = 1; i <= n; ++i) bfs(i);
		while(q--){
			int w,z; cin >> w >> z;
			if(d[w][z] == N){
				cout << "impossible\n";
			}else{
				cout << d[w][z] << "\n";
			}
		}
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Runtime error 4 ms 724 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 16 ms 8404 KB Output is correct
4 Correct 12 ms 8404 KB Output is correct
5 Correct 17 ms 8348 KB Output is correct
6 Correct 48 ms 9212 KB Output is correct
7 Correct 119 ms 9904 KB Output is correct
8 Correct 140 ms 11036 KB Output is correct
9 Correct 727 ms 12400 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 16 ms 8404 KB Output is correct
4 Correct 12 ms 8404 KB Output is correct
5 Correct 17 ms 8348 KB Output is correct
6 Correct 48 ms 9212 KB Output is correct
7 Correct 119 ms 9904 KB Output is correct
8 Correct 140 ms 11036 KB Output is correct
9 Correct 727 ms 12400 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 18 ms 8316 KB Output is correct
13 Correct 12 ms 8388 KB Output is correct
14 Correct 19 ms 8416 KB Output is correct
15 Correct 44 ms 9076 KB Output is correct
16 Correct 125 ms 9948 KB Output is correct
17 Correct 137 ms 10980 KB Output is correct
18 Correct 766 ms 12604 KB Output is correct
19 Execution timed out 1562 ms 40952 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 16 ms 8404 KB Output is correct
4 Correct 12 ms 8404 KB Output is correct
5 Correct 17 ms 8348 KB Output is correct
6 Correct 48 ms 9212 KB Output is correct
7 Correct 119 ms 9904 KB Output is correct
8 Correct 140 ms 11036 KB Output is correct
9 Correct 727 ms 12400 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 17 ms 8424 KB Output is correct
13 Correct 13 ms 8404 KB Output is correct
14 Correct 17 ms 8356 KB Output is correct
15 Correct 56 ms 9116 KB Output is correct
16 Correct 119 ms 9952 KB Output is correct
17 Correct 139 ms 10952 KB Output is correct
18 Correct 729 ms 12412 KB Output is correct
19 Runtime error 3 ms 724 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 796 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Runtime error 4 ms 724 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -