Cod sursa(job #1206730)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 11 iulie 2014 00:05:12
Problema Lazy Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define Nmax 200005
#define DIM 666013

using namespace std;
char buffer[DIM];
int poz = DIM - 1;

void scan(long long &A)
{
    int sgn = 1;
    A = 0;
    while( ('0' > buffer[poz]  || buffer[poz] > '9') && buffer[poz] != '-')
        if(++poz == DIM) fread(buffer,1,DIM,stdin),poz = 0;
    while( '0' <= buffer[poz] && buffer[poz] <= '9' || buffer[poz] == '-')
    {
        if(buffer[poz] == '-')
            sgn *= -1;
        else
            A = A * 10 + buffer[poz] - 48;
        if(++poz == DIM)
            fread(buffer,1,DIM,stdin),poz = 0;
    }
    A *= sgn;
}


struct elem{
    long long cost,profit;
    int a,b,poz;
};
class cmp{
public:
    bool operator()(const elem &e1,const elem &e2)const
    {
        if(e1.cost == e2.cost)
            return e1.profit > e2.profit;
        return e1.cost < e2.cost;
    }
};
vector<elem> V;
int N,M,daddy[Nmax];

int whos_ur_daddy(int k)
{
    if(daddy[k] != k)
        daddy[k] = whos_ur_daddy(daddy[k]);
    return daddy[k];
}
void couple(int a,int b)
{
    daddy[daddy[a]] = daddy[b];
}

void read()
{
    long long aux;
    scan(aux);N = aux;
    scan(aux);M = aux;
    for(int i = 1; i <= N; ++i)
        daddy[i] = i;
    int a,b;
    long long c,d;
    for(int i = 1; i <= M; ++i)
    {
        scan(aux); a = aux;
        scan(aux); b = aux;
        scan(aux); c = aux;
        scan(aux); d = aux;
        elem e;
        e.a = a;
        e.b = b;
        e.cost = c;
        e.profit = d;
        e.poz = i;
        V.push_back(e);
    }
    sort(V.begin(),V.end(),cmp());
}

void solve()
{
    vector<int> sol;
    int x,y;
    for(int i = 0; i < M; ++i)
    {
        x = V[i].a;
        y = V[i].b;
        if(whos_ur_daddy(x) != whos_ur_daddy(y))
        {
            couple(x,y);
            sol.push_back(V[i].poz);
        }
    }
    sort(sol.begin(),sol.end());
    for(int i = 0; i <(int) sol.size(); ++i)
        printf("%d\n",sol[i]);
}

int main()
{
    freopen("lazy.in","r",stdin);
    freopen("lazy.out","w",stdout);

    read();
    solve();

    return 0;
}