Cod sursa(job #708345)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 6 martie 2012 19:02:11
Problema Lazy Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

typedef long long i64;

struct str
{
    int a,b,i;
    i64 x,y;
};

struct str_cmp
{
    bool operator()(str x,str y)
    {
        if (x.x==y.x)
            return x.y>y.y;
        else
            return x.x<x.y;
    };
};

const int N_MAX=200000;

int r[N_MAX+1],sol[N_MAX];
str e[N_MAX+1];

void upd_r(int x)
{
    stack <int> s;

    while (r[r[x]]!=r[x])
    {
        s.push(x);
        x=r[x];
    }

    while (!s.empty())
    {
        r[s.top()]=r[x];
        s.pop();
    }
}

int main()
{
    int n,m;

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

    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i)
    {
        e[i].i=i;
        scanf("%d%d%lld%lld",&e[i].a,&e[i].b,&e[i].x,&e[i].y);
    }
    sort(e+1,e+m+1,str_cmp());

    for (int i=1;i<=n;++i)
        r[i]=i;

    for (int i=1;i<=m;++i)
    {
        int x=e[i].a,y=e[i].b;

        upd_r(x);
        upd_r(y);

        if (r[x]!=r[y])
        {
            ++sol[0];
            sol[sol[0]]=e[i].i;
            r[r[x]]=r[y];
        }
    }

    sort(sol+1,sol+n);
    for (int i=1;i<n;++i)
        printf("%d\n",sol[i]);

    return 0;
}