CSES - Planet Queries I

Explanation

Construct a parent matrix (where $\texttt{parent}[i][d]$ is the $2^d$th parent of $i$). Then, we can answer each query by using binary jumping from the starting node based on the binary representation of the distance.

Since the query distances can be up to $10^9$, we set the maximum depth to $\lceil{\log_2{10^9}}\rceil = 30$.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
const int MAXD = 30;  // ceil(log2(10^9))

// number of planets and queries
int n, q;
// parent matrix where [i][j] corresponds to i's (2^j)th parent
int parent[MAXN][MAXD];