oj.uz

Submission #595661

# Submission time Handle Problem Language Result Execution time Memory
595661 2022-07-13T23:46:51 Z pedroslrey Event Hopping (BOI22_events) C++14
0 / 100
 294 ms 8452 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;
const int MAXK = 30;

vector<int> graph[MAXN];
int dp[MAXN][MAXK];
int dist[MAXN];

void dfs(int u) {
	for (int v: graph[u]) {
		dp[v][0] = u;
		for (int k = 1; k < MAXK; ++k)
			dp[v][k] = dp[dp[v][k-1]][k-1];
		dist[v] = dist[u] + 1;
		dfs(v);
	}
}

int lca(int a, int b) {
	if (dist[a] > dist[b]) swap(a, b);

	int d = dist[b] - dist[a];
	for (int k = 0; k < MAXK; ++k)
		if (d & (1 << k)) b = dp[b][k];

	if (a == b) return a;

	for (int k = MAXK - 1; k >= 0; --k)
		if (dp[a][k] != dp[b][k]) {
			a = dp[a][k];
			b = dp[b][k];
		}

	return dp[a][0];
}

int main() {
	int n, q;
	cin >> n >> q;

	vector<pair<int, int>> events;
	for (int i = 1; i <= n; ++i) {
		int a, b;
		cin >> a >> b;

		events.emplace_back(a, i);
		events.emplace_back(b, -i);
	}

	sort(events.begin(), events.end());

	set<int> atual;
	for (auto [u, t]: events) {
		if (t > 0) atual.insert(t);
		else {
			atual.erase(-t);
			if (!atual.empty()) {
				graph[*atual.begin()].push_back(-t);
				cerr << -t << " -> " << *atual.begin() << "\n";
			}
		}
	}

	for (int i = 1; i <= n; ++i)
		if (dp[i][0] == 0) dfs(i);

	for (int i = 0; i < q; ++i) {
		int a, b;
		cin >> a >> b;

		int c = lca(a, b);

		if (c != b) cout << "impossible\n";
		else cout << dist[b] - dist[a] << "\n";
	}
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:56:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |  for (auto [u, t]: events) {
      |            ^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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