Cod sursa(job #2028520)

Utilizator Liviu_Ionut_MoantaMoanta Ionut Liviu Liviu_Ionut_Moanta Data 27 septembrie 2017 23:12:37
Problema Lazy Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("lazy.in");
ofstream fout("lazy.out");
long long n,m,i,l,a,b,c1,c2,x,y,rx,ry;
long long w[200005],sol[200005];
pair < pair <long long,long long> ,pair <long long, pair <long long,long long> > > v[200005];
long long f(long long k){
    while(w[k]>0){
        k=w[k];
    }
    return k;
}
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c1>>c2;
        v[i].first.first=c1;
        v[i].first.second=-c2;
        v[i].second.first=a;
        v[i].second.second.first=b;
        v[i].second.second.second=i;
    }
    sort(v+1,v+m+1);
    for(i=1;i<=n;i++){
        w[i]=-1;
    }
    l=0;
    for(i=1;i<=m;i++){
        x=v[i].second.first;
        y=v[i].second.second.first;
        rx=f(x);
        ry=f(y);
        if(rx!=ry){
            sol[++l]=v[i].second.second.second;
            if(w[rx]<w[ry]){
                w[rx]+=w[ry];
                w[ry]=rx;
            }
            else{
                w[ry]+=w[rx];
                w[rx]=ry;
            }
        }
    }
    for(i=1;i<=l;i++){
        fout<<sol[i]<<"\n";
    }
    return 0;
}