Cod sursa(job #2028804)

Utilizator luanastLuana Strimbeanu luanast Data 28 septembrie 2017 18:05:50
Problema Lazy Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("lazy.in");
ofstream fout ("lazy.out");
int x,y,i,ii,m,n,q,rx,ry,k, T[200001], sol[200001];

int rad (int x){
    while(T[x]>0){
        x=T[x];
    }
    return x;
}

struct graf{
    int st,dr,i;
    long long c1,c2;
}L[200001];

bool cmp(graf x, graf y){
    if(x.c1==y.c2)
        return x.c2>y.c2;
    return x.c1<y.c1;
}

int main(){
    fin>>n>>m;
    for(i=1;i<=n;i++){
        T[i]=-1;
    }
    for(i=1;i<=m;i++){
        fin>>L[i].st>>L[i].dr>>L[i].c1>>L[i].c2;
        L[i].i=i;
    }
    sort(L+1,L+m+1,cmp);
    for(i=1;i<=m;i++){
        rx=rad(L[i].st);
        ry=rad(L[i].dr);
        if(rx!=ry){
            sol[++k]=L[i].i;
            if(rx>ry){
                T[rx]+=T[ry];
                T[ry]=rx;
            }
            else{
                T[ry]+=T[rx];
                T[rx]=ry;
            }
        }
    }
    for(i=1;i<=k;i++){
        fout<<sol[i]<<"\n";
    }
    return 0;
}