Submission #867707

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

events

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
vector <int> adj[MAXN];
pair <int, int> arr[MAXN];
int main () {
	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);
			}
		}
	}
	while (q--) {
		int a, b;
		cin >> a >> b;
		int dist[MAXN];
		for (int i = 1; i <= n; i++) {
			dist[i] = 1e8;
		}
		dist[a] = 0;
		queue <int> cur; cur.push(a);
		while (!cur.empty()) {
			auto k = cur.front();
			cur.pop();
			for (auto j : adj[k]) {
				if (dist[j] > dist[k] + 1) {
					dist[j] = dist[k] + 1;
					cur.push(j);
				}
			}
		}
		if (dist[b] > n) {
			cout << "impossible\n";
		} else {
			cout << dist[b] << '\n';
		}
	}
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3676 KB	Output is correct
2	Execution timed out	1587 ms	6408 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	3676 KB	Output is correct
2	Correct	1 ms	3676 KB	Output is correct
3	Correct	6 ms	3828 KB	Output is correct
4	Correct	5 ms	3676 KB	Output is correct
5	Correct	7 ms	3932 KB	Output is correct
6	Correct	8 ms	4444 KB	Output is correct
7	Correct	18 ms	5428 KB	Output is correct
8	Correct	17 ms	6488 KB	Output is correct
9	Correct	69 ms	7772 KB	Output is correct

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3676 KB	Output is correct
2	Correct	1 ms	3676 KB	Output is correct
3	Correct	6 ms	3828 KB	Output is correct
4	Correct	5 ms	3676 KB	Output is correct
5	Correct	7 ms	3932 KB	Output is correct
6	Correct	8 ms	4444 KB	Output is correct
7	Correct	18 ms	5428 KB	Output is correct
8	Correct	17 ms	6488 KB	Output is correct
9	Correct	69 ms	7772 KB	Output is correct
10	Correct	1 ms	3676 KB	Output is correct
11	Correct	1 ms	3676 KB	Output is correct
12	Correct	6 ms	3672 KB	Output is correct
13	Correct	5 ms	3676 KB	Output is correct
14	Correct	5 ms	3676 KB	Output is correct
15	Correct	8 ms	4444 KB	Output is correct
16	Correct	16 ms	5236 KB	Output is correct
17	Correct	17 ms	6488 KB	Output is correct
18	Correct	69 ms	7636 KB	Output is correct
19	Execution timed out	1541 ms	33872 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	3676 KB	Output is correct
2	Correct	1 ms	3676 KB	Output is correct
3	Correct	6 ms	3828 KB	Output is correct
4	Correct	5 ms	3676 KB	Output is correct
5	Correct	7 ms	3932 KB	Output is correct
6	Correct	8 ms	4444 KB	Output is correct
7	Correct	18 ms	5428 KB	Output is correct
8	Correct	17 ms	6488 KB	Output is correct
9	Correct	69 ms	7772 KB	Output is correct
10	Correct	1 ms	3672 KB	Output is correct
11	Correct	1 ms	3676 KB	Output is correct
12	Correct	6 ms	3932 KB	Output is correct
13	Correct	5 ms	3676 KB	Output is correct
14	Correct	5 ms	3928 KB	Output is correct
15	Correct	8 ms	4444 KB	Output is correct
16	Correct	16 ms	5212 KB	Output is correct
17	Correct	16 ms	6488 KB	Output is correct
18	Correct	68 ms	7772 KB	Output is correct
19	Execution timed out	1557 ms	5972 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	1574 ms	4212 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	3676 KB	Output is correct
2	Execution timed out	1587 ms	6408 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-