Skip to Content
CTRL K

Mootube

Pista 1

Pensemos en los NN videos y las N−1N - 1 relaciones entre ellos. ¿Qué estructura de datos crees que puede guardar y procesar mejor esa información?

Pista 2

Imaginemos buscar a mano en un árbol de videos para una sola consulta. ¿Qué observaciones podemos hacer sobre cómo el valor de relevancia influye en nuestro proceso de decisión al elegir los videos relevantes?

Solución

Análisis oficial (Java) 

Explicación

Representamos los videos y sus relaciones usando un árbol, donde cada nodo corresponde a un video y las aristas denotan la relevancia entre ellos.

Para cada consulta, hacemos una búsqueda en profundidad empezando desde el video dado, recorriendo solo las aristas que son mayores o iguales que el umbral de relevancia.

Esto nos permite identificar de forma eficiente todos los videos que satisfacen el umbral, así que contamos cada video válido y al final imprimimos el total calculado.

Implementación

La implementación usa DFS en vez de BFS, pero la esencia sigue siendo la misma.

Complejidad temporal: O(N⋅Q)\mathcal{O}(N \cdot Q)

#include <bits/stdc++.h>
using namespace std;
 
vector<vector<pair<int, int>>> neighbors;
vector<bool> visited;
int threshold;
int num_reachable;
 
/** busca todos los vértices que se pueden alcanzar a través del video actual v */
void search_videos(int v) {
	visited[v] = true;
	for (const pair<int, int> &n : neighbors[v]) {
		/*
		 * solo visitamos videos no visitados cuya relevancia
		 * es mayor que el umbral actual
		 */
		if (!visited[n.first] && n.second >= threshold) {
			num_reachable++;
			search_videos(n.first);
		}
	}
}
 
int main() {
	freopen("mootube.in", "r", stdin);
	int video_num;
	int query_num;
	cin >> video_num >> query_num;
 
	neighbors = vector<vector<pair<int, int>>>(video_num);
	for (int e = 0; e < video_num - 1; e++) {
		int a, b;
		int relevance;
		cin >> a >> b >> relevance;
		a--;
		b--;
		neighbors[a].push_back({b, relevance});
		neighbors[b].push_back({a, relevance});
	}
 
	freopen("mootube.out", "w", stdout);
	for (int q = 0; q < query_num; q++) {
		int start;
		cin >> threshold >> start;
		start--;
 
		// reiniciamos las variables globales para la consulta actual
		num_reachable = 0;
		visited = vector<bool>(video_num);
		search_videos(start);
 
		cout << num_reachable << '\n';
	}
}
import java.io.*;
import java.util.*;
 
public class MooTube {
	private static class Edge {
		int to;
		int relevance;
		public Edge(int to, int relevance) {
			this.to = to;
			this.relevance = relevance;
		}
	}
 
	static int threshold;
	static int numReachable;
	static boolean[] visited;
	static List<Edge>[] neighbors;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("mootube");
		int videoNum = io.nextInt();
		int queryNum = io.nextInt();
 
		neighbors = new ArrayList[videoNum];
		for (int v = 0; v < videoNum; v++) { neighbors[v] = new ArrayList<>(); }
		for (int e = 0; e < videoNum - 1; e++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			int relevance = io.nextInt();
			neighbors[a].add(new Edge(b, relevance));
			neighbors[b].add(new Edge(a, relevance));
		}
 
		for (int q = 0; q < queryNum; q++) {
			threshold = io.nextInt();
			int start = io.nextInt() - 1;
 
			// reiniciamos las variables globales para la consulta actual
			numReachable = 0;
			visited = new boolean[videoNum];
			searchVideos(start);
 
			io.println(numReachable);
		}
 
		io.close();
	}
 
	/** busca todos los vértices que se pueden alcanzar a través del video actual v */
	static void searchVideos(int v) {
		visited[v] = true;
		for (Edge e : neighbors[v]) {
			/*
			 * solo visitamos videos no visitados cuya relevancia
			 * es mayor que el umbral actual
			 */
			if (!visited[e.to] && e.relevance >= threshold) {
				numReachable++;
				searchVideos(e.to);
			}
		}
	}
 
	// CodeSnip{Kattio}
}
import sys
 
sys.setrecursionlimit(int(1e9))
 
 
def search_videos(v: int, threshold: int) -> None:
	"""Busca todos los vértices que se pueden alcanzar a través del vértice actual v"""
	global num_reachable
	visited[v] = True
	for n in neighbors[v]:
		# Solo visitamos vértices no visitados cuya relevancia es mayor que el umbral actual
		if not visited[n[0]] and n[1] >= threshold:
			num_reachable += 1
			search_videos(n[0], threshold)
 
 
with open("mootube.in", "r") as read:
	with open("mootube.out", "w") as write:
		neighbors = []
		visited = []
		num_reachable = 0
		video_num, query_num = map(int, read.readline().split())
		neighbors = [[] for _ in range(video_num + 1)]
		for _ in range(video_num - 1):
			a, b, relevance = map(int, read.readline().split())
			a -= 1
			b -= 1
			neighbors[a].append((b, relevance))
			neighbors[b].append((a, relevance))
 
		for _ in range(query_num):
			threshold, start = map(int, read.readline().split())
			start -= 1
 
			# Reiniciamos las variables globales para la consulta actual
			num_reachable = 0
			visited = [False] * video_num
			search_videos(start, threshold)
 
			write.write(f"{num_reachable}\n")
Fundamentos