Budgetting bridges

#include <iostream>
#include <map>
#include <vector>
using namespace std;

const int MN = 1<<20;

struct Edge {
	int a,b,c;
};
Edge es[MN];
bool fail[MN];
map<pair<int,int>, int> e2p;
map<int, vector<Edge>> p2e;

map<int,map<int, vector<Edge>>> p2m2e;

int ps[MN];
int getP(int n) {
	if (ps[n]==n) return n;
	return ps[n] = getP(ps[n]);
}

vector<int> tes[MN];
int used[MN];
int T=1;
bool cdfs(int n, int f) {
	if (used[n]==T) return 1;
	used[n]=T;
	int x=0;
	for(int t: tes[n]) {
		if (t==f) {
			if (x>0) return 0;
			x++;
			continue;
		}
		if (cdfs(t, n)) return 1;
	}
	return 0;
}

int main() {
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=0; i<=n; ++i) ps[i]=i;
	for(int i=0; i<m; ++i) {
		int a,b,c;
		cin>>a>>b>>c;
		if (a>b) swap(a,b);
		e2p[make_pair(a,b)] = c;
		p2e[c].push_back({a,b,c});
	}
	for(int i=0; i<k; ++i) {
		int e;
		cin>>e;
		for(int j=0; j<e; ++j) {
			int a,b;
			cin>>a>>b;
			if (a>b) swap(a,b);
			int p = e2p[make_pair(a,b)];
			p2m2e[p][i].push_back({a,b,p});
		}
	}

	vector<int> prices;
	for(const auto& pe: p2e) {
		for(const auto& r: p2m2e[pe.first]) {
			T++;
			for(Edge e: r.second) {
				int a = getP(e.a);
				int b = getP(e.b);
				if (a==b) {
					fail[r.first] = 1;
				}
				tes[a].clear();
				tes[b].clear();
			}
			for(Edge e: r.second) {
				int a = getP(e.a);
				int b = getP(e.b);
				tes[a].push_back(b);
				tes[b].push_back(a);
			}
			for(Edge e: r.second) {
				int a = getP(e.a);
				if (used[a]==T) continue;
				if (cdfs(a, -1)) fail[r.first] = 1;
			}
		}
		for(auto e: pe.second) {
			ps[getP(e.a)] = getP(e.b);
		}
	}

	for(int i=0; i<k; ++i) {
		cout<<(fail[i]?"NO\n":"YES\n");
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED