oj.uz

Submission #867702

# Submission time Handle Problem Language Result Execution time Memory
867702 2023-10-29T09:23:33 Z TAhmed33 Event Hopping (BOI22_events) C++
0 / 100
 412 ms 31896 KB 
#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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 31896 KB Output is correct
2 Correct 373 ms 31828 KB Output is correct
3 Correct 390 ms 31744 KB Output is correct
4 Correct 323 ms 24544 KB Output is correct
5 Correct 363 ms 29676 KB Output is correct
6 Incorrect 354 ms 27620 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

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