2018 - Bitaro's Birthday

Explicación

Resolvamos primero la subtarea $q = 1$ . Invertimos el grafo de modo que, en esta consulta, resolvemos el camino más largo desde $t$ hasta un nodo no bloqueado. Aquí, podemos usar DP para calcular el camino más largo hacia cada nodo posible $s$ . Si $\texttt{dp}_i$ guarda el camino más largo de $t$ a $i$ , entonces $\texttt{dp}_v = \max(\texttt{dp}_v, \texttt{dp}_u + 1)$ , sobre todo $v$ donde $u$ y $v$ están conectados por una arista y es alcanzable desde $t$ en el grafo invertido. Como se garantiza que $v < u$ , esto se puede hacer con un solo barrido.

Ahora, introduzcamos descomposición por raíz cuadrada. La variable en cuestión es el número de nodos bloqueados, denotado como $y$ . Denotemos $B = \sqrt{10^5}$ y supongamos que todas las consultas tienen $y \geq B$ . Como la suma de $y$ sobre todas las consultas está acotada por $10^5$ , no puede haber más de $\frac{10^5}{B} = B$ consultas. El número de consultas es lo bastante pequeño como para ejecutar un algoritmo de DP en $\mathcal{O}(n)$ cada vez, lo que lleva a un tiempo de ejecución $\mathcal{O}({Bn})$ .

Para manejar las consultas con $y < B$ , hay que hacer algo de preprocesamiento. Para cada nodo, podemos guardar los $B$ caminos más largos que terminan en ese nodo, cada uno originado en un nodo inicial distinto. Esto hay que hacerlo con una poda cuidadosa de caminos de distintas longitudes que se originan en el mismo nodo. Esta precomputación es aproximadamente $\mathcal{O}(Bm + n \log(Bn))$ , ya que hay que ordenar los caminos más largos después de procesar cada nodo. Para responder las consultas, podemos recorrer los $B$ caminos más largos de $t$ y hallar el más largo que empieza en un nodo no bloqueado. Esto también tomará tiempo $\mathcal{O}({Bn})$ .

Implementación

Complejidad temporal: $\mathcal{O}(Bm + n \log(Bn) + Bn)$

C++


#include <bits/stdc++.h>
using namespace std;
const int SQ = 100;  // cutoff for sqrt decomp
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m, q;
	cin >> n >> m >> q;
	vector<vector<int>> rg(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		rg[--v].push_back(--u);
	}
 
	// stores the 100 longest paths ending at i
	vector<vector<pair<int, int>>> path_sizes(n);
	vector<int> from(n, -1);  // longest path starting at that node
 
	for (int i = 0; i < n; i++) {
		path_sizes[i].push_back({0, i});
		vector<int> from_indicies;
 
		for (int j : rg[i]) {
			for (auto [dist, idx] : path_sizes[j]) {
				if (from[idx] == -1) {
					// if we haven't gotten a path from this index yet
					from_indicies.push_back(idx);
					from[idx] = dist + 1;
				} else {
					// take max with already processed dist
					from[idx] = max(from[idx], dist + 1);
				}
			}
		}
 
		for (int j : from_indicies) { path_sizes[i].push_back({from[j], j}); }
		sort(path_sizes[i].rbegin(), path_sizes[i].rend());
		// pop until sqrt paths
		while (path_sizes[i].size() > SQ) { path_sizes[i].pop_back(); }
 
		// reset
		for (int j : from_indicies) { from[j] = -1; }
	}
 
	vector<bool> blocked(n);
	for (int query = 0; query < q; query++) {
		int t, y;
		cin >> t >> y;
		t--;
 
		vector<int> c(y);
		for (int i = 0; i < y; i++) {
			cin >> c[i];
			blocked[--c[i]] = true;
		}
 
		int ans = -1;
		if (y >= SQ) {
			// brute force dp since number of queries is bounded by sqrt
			vector<int> dp(t + 1, -1);  // dp[i] stores longest path ending at i
			dp[t] = 0;
			for (int i = t; i >= 0; i--) {
				if (dp[i] == -1) { continue; }
				if (!blocked[i]) { ans = max(ans, dp[i]); }
				for (int j : rg[i]) { dp[j] = max(dp[j], dp[i] + 1); }
			}
		} else {
			for (auto [dist, idx] : path_sizes[t]) {
				if (!blocked[idx]) {
					ans = dist;
					break;
				}
			}
		}
 
		cout << ans << "\n";
 
		for (int i : c) { blocked[i] = false; }
	}
}