Cod sursa(job #1238159)

Utilizator enedumitruene dumitru enedumitru Data 5 octombrie 2014 20:27:41
Problema Lazy Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<cstdio>
#include<algorithm>
#define Nmax 200005
using namespace std;
struct element {int a,b,poz; long long c1,c2;} v[Nmax];
int i,n,m,p1,p2,p[Nmax];
bool cmp(element a, element b)
{	return ((a.c1<b.c1) || ((a.c1==b.c1)&&(a.c2>b.c2)));}
int par(int a)
{   if(p[a]!=a)
        p[a]=par(p[a]);
    return p[a];
}
int main()
{   freopen("lazy.in","r",stdin); freopen("lazy.out","w",stdout);
    scanf("%ld %ld",&n,&m);
    for(i=1;i<=m;i++)
    {   scanf("%d %d %lld %lld", &v[i].a,&v[i].b,&v[i].c1,&v[i].c2);
        v[i].poz=i;
        p[v[i].a]=v[i].a; p[v[i].b]=v[i].b;
    }
    sort(v+1,v+1+m,cmp);
    for (i=1;i<=m;i++)
    {   p1=par(v[i].a); p2=par(v[i].b);
        if(p1!=p2)
        {   p[p2]=p1;
            printf("%d\n",v[i].poz);
        }
    }
    return 0;
}