Submission #867709

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
867709	2023-10-29T09:46:29 Z	TAhmed33	Event Hopping (BOI22_events)	C++	10 / 100	1500 ms	41084 KB

events

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 25;
vector <int> adj[MAXN];
pair <int, int> arr[MAXN];
int dist[MAXN][MAXN];
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		arr[i] = {l, r};
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			if (arr[i].second >= arr[j].first && arr[i].second <= arr[j].second) {
				adj[i].push_back(j);
			}
		}
	}
	for (int a = 1; a <= n; a++) {
		for (int i = 1; i <= n; i++) {
			dist[a][i] = 1e8;
		}
		dist[a][a] = 0;
		queue <int> cur; cur.push(a);
		while (!cur.empty()) {
			auto k = cur.front();
			cur.pop();
			for (auto j : adj[k]) {
				if (dist[a][j] > dist[a][k] + 1) {
					dist[a][j] = dist[a][k] + 1;
					cur.push(j);
				}
			}
		}
	}
	while (q--) {
		int a, b;
		cin >> a >> b;
		if (dist[a][b] > n) {
			cout << "impossible\n";
		} else {
			cout << dist[a][b] << '\n';
		}
	}
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Runtime error	6 ms	1112 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	552 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	11 ms	21204 KB	Output is correct
4	Correct	9 ms	21084 KB	Output is correct
5	Correct	11 ms	21200 KB	Output is correct
6	Correct	41 ms	21844 KB	Output is correct
7	Correct	117 ms	22612 KB	Output is correct
8	Correct	145 ms	24084 KB	Output is correct
9	Correct	744 ms	25184 KB	Output is correct

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	552 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	11 ms	21204 KB	Output is correct
4	Correct	9 ms	21084 KB	Output is correct
5	Correct	11 ms	21200 KB	Output is correct
6	Correct	41 ms	21844 KB	Output is correct
7	Correct	117 ms	22612 KB	Output is correct
8	Correct	145 ms	24084 KB	Output is correct
9	Correct	744 ms	25184 KB	Output is correct
10	Correct	0 ms	600 KB	Output is correct
11	Correct	0 ms	600 KB	Output is correct
12	Correct	11 ms	21196 KB	Output is correct
13	Correct	8 ms	21084 KB	Output is correct
14	Correct	11 ms	21084 KB	Output is correct
15	Correct	42 ms	21980 KB	Output is correct
16	Correct	118 ms	22804 KB	Output is correct
17	Correct	139 ms	23840 KB	Output is correct
18	Correct	800 ms	25416 KB	Output is correct
19	Execution timed out	1541 ms	41084 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	552 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	11 ms	21204 KB	Output is correct
4	Correct	9 ms	21084 KB	Output is correct
5	Correct	11 ms	21200 KB	Output is correct
6	Correct	41 ms	21844 KB	Output is correct
7	Correct	117 ms	22612 KB	Output is correct
8	Correct	145 ms	24084 KB	Output is correct
9	Correct	744 ms	25184 KB	Output is correct
10	Correct	0 ms	604 KB	Output is correct
11	Correct	0 ms	604 KB	Output is correct
12	Correct	11 ms	21068 KB	Output is correct
13	Correct	8 ms	21080 KB	Output is correct
14	Correct	11 ms	21080 KB	Output is correct
15	Correct	41 ms	21840 KB	Output is correct
16	Correct	118 ms	22612 KB	Output is correct
17	Correct	140 ms	23632 KB	Output is correct
18	Correct	751 ms	25172 KB	Output is correct
19	Runtime error	8 ms	1368 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	7 ms	1372 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	600 KB	Output is correct
2	Runtime error	6 ms	1112 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-