oj.uz

Submission #745914

# Submission time Handle Problem Language Result Execution time Memory
745914 2023-05-21T09:37:37 Z vjudge1 Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 3972 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct event {
	int st, en, id;
};

const int maxn = 100010;
int nxt[maxn][20];
int d[maxn];

vector<int> g[maxn];
int bfs(int from, int to) {
	fill(d, d + maxn, 0);
	d[from] = 1;
	queue<int> q;
	q.push(from);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i : g[x]) {
			if (d[i] == 0) {
				q.push(i);
				d[i] = d[x] + 1;
			}
		}
	}
	return d[to];
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	vector<event> e(n+1);
	for (int i = 1; i <= n; i++) {
		cin >> e[i].st >> e[i].en;
		e[i].id = i;
	}
	/*e.push_back({ (int)1e9+1, (int)1e9 + 1 });
	for (int i = 0; i < 20; i++) {
		nxt[n + 1][i] = n + 1;
	}
	vector<int> pos(n + 1);
	sort(e.begin()+1, e.end(), [](event& a, event& b) {return a.en < b.en || (a.en==b.en && a.st < b.st); });
	int mn = n + 1;
	for (int i = n; i > 0; i--) {
		pos[e[i].id] = i;
		/*int l = i, r = n + 2;
		while (l + 1 < r) {
			int m = (l + r) / 2;
			if (e[m].st <= e[i].en)l = m;
			else r = m;
		}
		nxt[i][0] = (e[mn].st <= e[i].en ? mn : i);
		for (int j = 1; j < 20; j++) {
			nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
		}
		if (e[i].st < e[mn].st)mn = i;
	}*/

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (j == i)continue;
			if (e[i].st <= e[j].st && e[j].st <= e[i].en)g[i].push_back(j);
		}
	}

	for (int i = 0; i < q; i++) {
		int s, E;
		cin >> s >> E;
		int x = bfs(s, E);
		if (x)cout << x - 1 << '\n';
		else cout << "impossible\n";
		//s = pos[s];
		//E = pos[E];
		/*if (E == s) {
			cout << "0\n";
			continue;
		}
		if (e[s].en == e[E].en) {
			cout << "1\n";
			continue;
		}
		if (E < s) {
			cout << "impossible\n";
			continue;
		}
		int ans = 0;
		for (int i = 19; i >= 0; i--) {
			if (nxt[s][i] < E) {
				ans += (1 << i);
				s = nxt[s][i];
			}
		}
		if (nxt[s][0] != E) {
			cout << "impossible\n";
			continue;
		}
		cout << ans + 1 << '\n';*/

	}
}

Compilation message

events.cpp:55:3: warning: "/*" within comment [-Wcomment]
   55 |   /*int l = i, r = n + 2;
      |

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 10 ms 3084 KB Output is correct
4 Correct 7 ms 3028 KB Output is correct
5 Incorrect 8 ms 3028 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 10 ms 3084 KB Output is correct
4 Correct 7 ms 3028 KB Output is correct
5 Incorrect 8 ms 3028 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 10 ms 3084 KB Output is correct
4 Correct 7 ms 3028 KB Output is correct
5 Incorrect 8 ms 3028 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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