Submission #867704

#	Time	Username	Problem	Language	Result	Execution time	Memory
867704		TAhmed33	Event Hopping (BOI22_events)	C++98	0 / 100	462 ms	29544 KiB

events

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30