Cod sursa(job #2652766)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 25 septembrie 2020 17:36:50
Problema Lazy Scor 100
Compilator cpp-64 Status done
Runda apmtraining Marime 1.4 kb
#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;
ifstream fin("lazy.in");
ofstream fout("lazy.out");
long long m, el, i, f[200002],c,a,b,j,auxa,auxb ,nr;
long long sum;
pair <pair <long long, long long> , pair< int, pair <int, int > > > v[400002];
int z[400002], h[400002];

int calc(int nod)
{
    int aux=nod, a;
    while(f[nod]>0)
        nod=f[nod];
    while(f[aux]>0)
    {
        a=aux;
        aux=f[aux];
        f[a]=aux;
    }
    return nod;
}

int main(){
    fin>>el>>m;
    for(i=1;i<=el;i++)
        f[i]=-1;
    for(i=1;i<=m;i++)
    {
        fin>>v[i].second.first>>v[i].second.second.first>>v[i].first.first>>v[i].first.second;
        v[i].first.second=-v[i].first.second;
        v[i].second.second.second=i;
    }
    sort(v+1, v+1+m);
    for(i=1;i<=m;i++)
    {
        a=v[i].second.first;
        b=v[i].second.second.first;
        auxa=calc(a);
        auxb=calc(b);
        if(auxa!=auxb)
        {
            if(f[auxa]<f[auxb])
            {
                f[auxa]+=f[auxb];
                f[auxb]=auxa;
            }
            else
            {
                f[auxb]+=f[auxa];
                f[auxa]=auxb;
            }
            nr++;
            z[nr]=v[i].second.second.second;
        }
    }
    for(i=1;i<=nr;i++)
        fout<<z[i]<<"\n";
    fin.close();
    fout.close();
    return 0;
}