Cod sursa(job #1307449)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 2 ianuarie 2015 12:20:42
Problema Lazy Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<bits/stdc++.h>
using namespace std;

struct cell
{
    int x,y,ind;
    long long c1,c2;
};

ifstream fin("lazy.in");
ofstream fout("lazy.out");

const int NMAX=200005;

int n,m,father[NMAX];
cell a[NMAX];
bitset<NMAX>viz;

inline bool cmp(const cell A,const cell B)
{
    if (A.c1==B.c1) return A.c2>B.c2;
    return A.c1<B.c1;
}

inline void Union(int x,int y)
{
    father[x]=y;
}

inline int Father(int x)
{
    int y,z;
    z=x;
    while (x!=father[x]) x=father[x];
    while (z!=father[x])
        {
            y=father[z];
            father[z]=x;
            z=y;
        }
    return x;
}

int main()
{
    int i,aux,baux;
    fin>>n>>m;
    for (i=1;i<=n;i++) father[i]=i;
    for (i=1;i<=m;i++)
        {
            a[i].ind=i;
            fin>>a[i].x>>a[i].y>>a[i].c1>>a[i].c2;
        }
    sort(a+1,a+m+1,cmp);
    for (i=1;i<=m;i++)
        {
            aux=Father(a[i].x);
            baux=Father(a[i].y);
            if (aux!=baux)
                {
                    viz[a[i].ind]=1;
                    Union(aux,baux);
                }
        }
    for (i=1;i<=m;i++)
        if (viz[i]!=0) fout<<i<<"\n";
    return 0;
}