제출 #867702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867702		TAhmed33	Event Hopping (BOI22_events)	C++98	0 / 100	412 ms	31896 KiB

events

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
struct DSU {
	int sze[MAXN], par[MAXN];
	void init () {
		for (int i = 1; i < MAXN; i++) {
			par[i] = i; sze[i] = 1;
		}
	}
	int find (int x) {
		return par[x] == x ? x : par[x] = find(par[x]);
	}
	void merge (int a, int b) {
		a = find(a); b = find(b);
		if (a == b) return;
		if (sze[a] > sze[b]) swap(a, b);
		sze[b] += sze[a];
		swap(a, b);
	}
} cur;
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 () {
	cur.init();
	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++) val[i] = i;
	for (int i = 1; i <= n; i++) {
		if (par[i] == -1) continue;
		if (par[par[i]] == i) {
			val[par[i]] = i;
			val[i] = i;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (par[i] == -1) continue;
		par[i] = val[par[i]];
		if (i == par[i]) par[i] = -1;
	}
	
	for (int i = 1; i <= n; i++) if (par[i] != -1) adj[val[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 (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