Skip to Content
CTRL K

Envy

Análisis oficial 

Explicación

Podemos resolver esto usando intuición de MST. En el algoritmo de Kruskal, hay que ordenar las aristas por peso no decreciente y unir vértices si aún no están en la misma componente. Aquí, podemos comprobar cada consulta usando este algoritmo procesando cada arista de cada consulta de forma offline.

A medida que consideramos aristas de peso no decreciente, podemos llevar un MST construido parcialmente. Una arista puede estar en un MST solo si ya procesamos todas las aristas de peso menor que esta y somos capaces de unir los extremos de la arista. Esto se debe a que las aristas del mismo peso son arbitrarias, así que si priorizamos considerar esta arista entonces se construye otro MST con el mismo peso total.

Procesamos todas las aristas en orden de peso no decreciente y, para cada consulta, unimos los extremos de todas las aristas que tienen este peso. Si alguna arista no cumple la condición, falla la consulta entera.

Implementación

Complejidad temporal: O(qlog⁡n+m+q)\mathcal{O}(q \log n + m + q)

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 5e5 + 1;  // usamos indexación desde uno
vector<int> edge_by_weight[MAXN];
// query_by_weight[weight][index of query] = {index of edges}
map<int, vector<int>> query_by_weight[MAXN];
 
struct DSU {
	vector<int> p, sz;
	// guarda uniones anteriores
	vector<pair<int &, int>> psnap, szsnap;
 
	DSU(int n) {
		p.resize(n);
		sz.resize(n, 1);
		iota(p.begin(), p.end(), 0);
	}
 
	int get(int x) { return x == p[x] ? x : get(p[x]); }
 
	void unite(int a, int b) {
		a = get(a);
		b = get(b);
		if (sz[a] < sz[b]) { swap(a, b); }
		if (a != b) {
			// guardamos esta operación de unión
			szsnap.push_back({sz[a], sz[a]});
			psnap.push_back({p[b], p[b]});
 
			p[b] = a;
			sz[a] += sz[b];
		}
	}
 
	bool sameset(int a, int b) { return get(a) == get(b); }
 
	int current() { return psnap.size(); }
 
	void rollback(int until) {
		while (szsnap.size() > until) {
			szsnap.back().first = szsnap.back().second;
			szsnap.pop_back();
			psnap.back().first = psnap.back().second;
			psnap.pop_back();
		}
	}
};
 
struct Edge {
	int u, v, w;
};
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	vector<Edge> edges;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		--u;
		--v;
		edges.push_back({u, v, w});
		edge_by_weight[w].push_back(i);
	}
 
	int q;
	cin >> q;
	vector<bool> ans(q, true);
	for (int i = 0; i < q; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int x;
			cin >> x;
			x--;
			query_by_weight[edges[x].w][i].push_back(x);
		}
	}
 
	DSU dsu(n);
	for (int weight = 1; weight < MAXN; weight++) {
		for (auto &query : query_by_weight[weight]) {
			int index = query.first;
			int snapshot = dsu.current();
			// intentamos fusionar cada una de estas aristas del mismo peso
			for (int edge : query.second) {
				if (dsu.sameset(edges[edge].u, edges[edge].v)) {
					/*
					 * los vértices ya estaban en el MST parcial
					 * así que esta consulta queda invalidada
					 */
					ans[index] = false;
				}
				dsu.unite(edges[edge].u, edges[edge].v);
			}
			// revertimos todas las fusiones para preparar la siguiente consulta
			dsu.rollback(snapshot);
		}
 
		/*
		 * ahora que se procesaron todas las consultas,
		 * seguimos construyendo el MST parcial con estas aristas
		 */
		for (int edge : edge_by_weight[weight]) {
			dsu.unite(edges[edge].u, edges[edge].v);
		}
	}
 
	for (int i = 0; i < q; i++) { cout << (ans[i] ? "YES" : "NO") << "\n"; }
}
Fundamentos