Cod sursa(job #2029846)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 30 septembrie 2017 15:44:12
Problema Lazy Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <algorithm>
#define DIM 200002
using namespace std;
long long n,m,i,x,y,k,rx,ry,t[DIM],sol[DIM];
pair < pair<long long,long long>, pair < long long , pair <long long,long long> >  > v[DIM];
long long rad (long long x){
    while (t[x] > 0)
        x = t[x];
    return x;
}
int main (){

    ifstream fin ("lazy.in");
    ofstream fout ("lazy.out");
    fin>>n>>m;
    for (i=1;i<=n;i++)
        t[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].second.second.second = i; // indicele
        v[i].first.second = -v[i].first.second;
    }
    sort (v+1,v+m+1);

    for (i=1;i<=m;i++){
        x = v[i].second.first;
        y = v[i].second.second.first;
        rx = rad (x);
        ry = rad (y);
        if (rx != ry){
            // unesc x cu y
            k++;
            sol[k] = v[i].second.second.second;
            if (t[rx] < t[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;
}