Submission #595657

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
595657	2022-07-13T23:10:23 Z	pedroslrey	Event Hopping (BOI22_events)	C++14	10 / 100	115 ms	4436 KB

events

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e3 + 10;

int ls[MAXN], rs[MAXN], dist[MAXN];
vector<int> graph[MAXN];
bool marc[MAXN];

void bfs(int u, int n) {
	for (int i = 0; i < n; ++i) {
		marc[i] = false;
		dist[i] = 0;
	}

	queue<int> q;
	q.push(u);
	marc[u] = true;

	while (!q.empty()) {
		int u = q.front(); q.pop();

		for (int v: graph[u])
			if (!marc[v]) {
				marc[v] = true;
				dist[v] = dist[u] + 1;
				q.push(v);
			}
	}
}

int main() {
	int n, q;
	cin >> n >> q;

	for (int i = 0; i < n; ++i)
		cin >> ls[i] >> rs[i];

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			if (i != j && ls[i] <= rs[j] && rs[j] <= rs[i])
				graph[j].push_back(i);

	for (int i = 0; i < q; ++i) {
		int a, b;
		cin >> a >> b;

		--a; --b;

		bfs(a, n);

		if (!marc[b]) cout << "impossible\n";
		else cout << dist[b] << "\n";
	}
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	2 ms	596 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	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	6 ms	340 KB	Output is correct
4	Correct	5 ms	340 KB	Output is correct
5	Correct	5 ms	340 KB	Output is correct
6	Correct	10 ms	1236 KB	Output is correct
7	Correct	19 ms	2136 KB	Output is correct
8	Correct	19 ms	3156 KB	Output is correct
9	Correct	94 ms	4436 KB	Output is correct

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	6 ms	340 KB	Output is correct
4	Correct	5 ms	340 KB	Output is correct
5	Correct	5 ms	340 KB	Output is correct
6	Correct	10 ms	1236 KB	Output is correct
7	Correct	19 ms	2136 KB	Output is correct
8	Correct	19 ms	3156 KB	Output is correct
9	Correct	94 ms	4436 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	6 ms	340 KB	Output is correct
13	Correct	5 ms	352 KB	Output is correct
14	Correct	5 ms	340 KB	Output is correct
15	Correct	10 ms	1236 KB	Output is correct
16	Correct	20 ms	2132 KB	Output is correct
17	Correct	26 ms	3236 KB	Output is correct
18	Correct	80 ms	4308 KB	Output is correct
19	Runtime error	1 ms	468 KB	Execution killed with signal 11
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	6 ms	340 KB	Output is correct
4	Correct	5 ms	340 KB	Output is correct
5	Correct	5 ms	340 KB	Output is correct
6	Correct	10 ms	1236 KB	Output is correct
7	Correct	19 ms	2136 KB	Output is correct
8	Correct	19 ms	3156 KB	Output is correct
9	Correct	94 ms	4436 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	6 ms	344 KB	Output is correct
13	Correct	4 ms	348 KB	Output is correct
14	Correct	5 ms	340 KB	Output is correct
15	Correct	10 ms	1228 KB	Output is correct
16	Correct	19 ms	2140 KB	Output is correct
17	Correct	28 ms	3156 KB	Output is correct
18	Correct	115 ms	4436 KB	Output is correct
19	Runtime error	2 ms	468 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	2 ms	472 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	212 KB	Output is correct
2	Runtime error	2 ms	596 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-