Skip to Content
CTRL K

Planet Queries I

Explicación

Construyamos una matriz de padres (donde parent[i][d]\texttt{parent}[i][d] es el 2d2^d-ésimo padre de ii). Luego, podemos responder cada consulta usando binary jumping desde el nodo de inicio según la representación binaria de la distancia.

Como las distancias de las consultas pueden ser hasta 10910^9, fijamos la profundidad máxima en ⌈log⁡2109⌉=30\lceil{\log_2{10^9}}\rceil = 30.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N\log N)

#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];
 
int jump(int a, int d) {
	for (int i = 0; i < MAXD; i++)
		if (d & (1 << i)) a = parent[a][i];
	return a;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	cin >> n >> q;
	for (int i = 1; i <= n; i++) { cin >> parent[i][0]; }
	// evaluate the parent matrix
	for (int d = 1; d < MAXD; d++)
		for (int i = 1; i <= n; i++) { parent[i][d] = parent[parent[i][d - 1]][d - 1]; }
	// process queries
	while (q--) {
		int a, d;
		cin >> a >> d;
		cout << jump(a, d) << '\n';
	}
}
import java.io.*;
import java.util.*;
 
public class PlanetQueries {
	static final int MAXLOG = 32;
	static int[][] parent;
 
	public static void main(String[] args) throws IOException {
		FastReader fr = new FastReader();
		StringBuilder sb = new StringBuilder();
 
		int n = fr.nextInt();
		int q = fr.nextInt();
 
		parent = new int[n + 1][MAXLOG];
 
		for (int i = 1; i <= n; i++) parent[i][0] = fr.nextInt();
 
		// Precompute binary lifting table
		for (int j = 1; j < MAXLOG; j++) {
			for (int i = 1; i <= n; i++) parent[i][j] = parent[parent[i][j - 1]][j - 1];
		}
 
		while (q-- > 0) {
			int u = fr.nextInt();
			int k = fr.nextInt();
 
			for (int j = 0; j < MAXLOG; j++) {
				if ((k & (1 << j)) != 0) u = parent[u][j];
			}
			sb.append(u).append('\n');
		}
 
		System.out.print(sb);
	}
 
	// FastReader using byte buffer
	static class FastReader {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1 << 16];
		private int ptr = 0, len = 0;
 
		private int readByte() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
 
		int nextInt() throws IOException {
			int c, sign = 1, val = 0;
			do { c = readByte(); } while (c <= ' ');
			if (c == '-') {
				sign = -1;
				c = readByte();
			}
			while (c > ' ') {
				val = val * 10 + (c - '0');
				c = readByte();
			}
			return val * sign;
		}
	}
}
Fundamentos