oj.uz

Submission #867704

# Submission time Handle Problem Language Result Execution time Memory
867704 2023-10-29T09:32:15 Z TAhmed33 Event Hopping (BOI22_events) C++
0 / 100
 462 ms 29544 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
int n, q;
vector <int> arr[MAXN];
set <vector <int>> dd;
int par[MAXN];
int dep[MAXN], in[MAXN], out[MAXN];
int t = 0;
vector <int> adj[MAXN];
int val[MAXN];
void dfs (int pos) {
	in[pos] = ++t;
	for (auto j : adj[pos]) {
		dep[j] = 1 + dep[pos];
		dfs(j);
	}
	out[pos] = t;
}
int main () {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		arr[i] = {l, r, i};
		dd.insert({l, r, i});
	}
	for (int i = 1; i <= n; i++) {
		dd.erase(arr[i]);
		if (dd.empty()) {
			par[i] = -1; continue;
		}
		auto g = dd.upper_bound({arr[i][1], (int)1e9, 0});
		if (g == dd.begin()) {
			par[i] = -1;
		} else {
			g--;
			int l = (*g)[0], r = (*g)[1];
			if (l > arr[i][1] || r < arr[i][1]) {
				par[i] = -1;
			} else {
				par[i] = (*g)[2];
			}
		}
		dd.insert(arr[i]);
	}
	for (int i = 1; i <= n; i++) {
		if (par[i] != -1 && par[par[i]] == i) {
			par[par[i]] = -1; par[i] = -1; 
		}
	}
	for (int i = 1; i <= n; i++) if (par[i] != -1) {
		adj[par[i]].push_back(i);
	}
	for (int i = 1; i <= n; i++) if (par[i] == -1) dfs(i);
	while (q--) {
		int a, b;
		cin >> a >> b; 
		if (a == b) {
			cout << "0\n";
			continue;
		}
		if (arr[a][1] == arr[b][1]) {
			cout << "1\n";
			continue;
		}
		if (in[a] > in[b] && out[a] <= out[b]) {
			cout << dep[a] - dep[b] << '\n';
		} else {
			cout << "impossible\n";
		}
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Incorrect 3 ms 5152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Incorrect 3 ms 5152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Incorrect 3 ms 5152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 29252 KB Output is correct
2 Correct 428 ms 29392 KB Output is correct
3 Correct 399 ms 29544 KB Output is correct
4 Correct 392 ms 21672 KB Output is correct
5 Correct 459 ms 27340 KB Output is correct
6 Incorrect 462 ms 25236 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -