Skip to Content
CTRL K

Ski Slope

Análisis oficial (C++) 

Explicación

Los waypoints y las pistas de esquí forman un árbol enraizado en el nodo 11, ya que cada waypoint tiene exactamente un padre (excepto la raíz). Así, cada camino de un nodo a la raíz es único. A cada arista se le asigna un valor de dificultad y de disfrute, y debemos responder MM consultas para hallar el disfrute total máximo de un camino de un nodo a la raíz, tal que a lo sumo cc aristas tengan dificultad mayor que ss.

Procesamos el árbol en orden creciente de nodos. Empezamos con el nodo 11 teniendo la lista de dificultades [0][0] y disfrute total 00. Luego, para el nodo ii, su camino a la raíz es el camino del padre pip_i más la arista (pi,i)(p_i, i). Como pi<ip_i < i, podemos construir de forma incremental la información del nodo ii usando lo que ya calculamos para su padre.

La observación clave es que la condición de que a lo sumo cc aristas tengan dificultad mayor que ss equivale a decir que la (c+1)(c + 1)-ésima mayor dificultad en el camino es ≤s\le s. Debido a la restricción especial c≤10c \le 10, solo necesitamos llevar las once mayores dificultades de cada camino. Cualquier dificultad menor es irrelevante para decidir si se cumple la restricción. Para cada nodo, mantenemos estas dificultades principales junto con el disfrute total del camino. Para cada cc, guardamos pares de (la (c+1)(c + 1)-ésima mayor dificultad, disfrute) de todos los nodos y los ordenamos por dificultad. Para responder una consulta (s,c)(s, c), hacemos búsqueda binaria de la dificultad en la lista correspondiente al cc-ésimo valor para hallar el máximo índice donde la dificultad es a lo sumo ss. La respuesta es entonces el máximo disfrute del prefijo hasta ese índice, que se puede obtener de forma eficiente precomputando máximos de prefijos.

Implementación

Complejidad temporal: O(NClog⁡N+Mlog⁡N)\mathcal{O}(NC\log N+M\log N)

import bisect
import itertools
 
n = int(input())
waypoints = [[[0], 0] for i in range(n)]
for waypoint in range(1, n):
	parent, difficulty, enjoyment = map(int, input().split())
	waypoints[waypoint][0] = sorted(waypoints[parent - 1][0][:] + [difficulty])[-11:]
	waypoints[waypoint][1] = waypoints[parent - 1][1] + enjoyment
 
top_11_difficulties = [[] for i in range(11)]
pref_max = []
for courage in range(11):
	for waypoint in range(1, n):
		if len(waypoints[waypoint][0]) > courage:
			top_11_difficulties[courage].append(
				[waypoints[waypoint][0][-courage - 1], waypoints[waypoint][1]]
			)
	top_11_difficulties[courage].sort()
	pref_max.append(
		list(itertools.accumulate([x[1] for x in top_11_difficulties[courage]], max))
	)
 
m = int(input())
for friend in range(m):
	skill, courage = map(int, input().split())
	max_enjoyment = 0
	max_index = bisect.bisect(top_11_difficulties[courage], [skill, float("inf")]) - 1
	if max_index >= 0:
		max_enjoyment = pref_max[courage][max_index]
	print(max_enjoyment)
Fundamentos