Cod sursa(job #728964)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 29 martie 2012 09:51:18
Problema Lazy Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

ifstream in("lazy.in");
ofstream out("lazy.out");

struct muc {
	long long d,c;
	int a,b,nr;
};

const int N = 200010;

int n,mm,tata[N];
vector<int> mu;
muc m[N];

inline bool cmp(muc a, muc b) {
	return a.d==b.d ? a.c>b.c : a.d<b.d;
}

inline int radacina(int nod) {
	if(!tata[nod])
		return nod;
	
	int rez = radacina(tata[nod]);
	tata[nod] = rez;
	return rez;
}

int main() {
	int i,x,y;
	
	in >> n >> mm;
	
	for(i=1;i<=mm;++i)
		in >> m[i].a >> m[i].b >> m[i].d >> m[i].c, m[i].nr = i;
	
	sort(m+1, m+mm+1, cmp);
	
	for(i = 1; i<=mm; ++i) {
		x = radacina(m[i].a);
		y = radacina(m[i].b);
		
		if(x!=y) {
			mu.push_back(m[i].nr);
			tata[y] = x;
		}
	}
	
	sort(&mu[1], &mu[mu.size()]);
	
	for(i=0;i!=mu.size();++i)
		out << mu[i] << "\n";
	
	return 0;
}