Cod sursa(job #887027)

Utilizator misinozzz zzz misino Data 23 februarie 2013 14:57:45
Problema Lazy Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("lazy.in");
ofstream g("lazy.out");
int i,n,x,y,nr,m,sol[200100],t[200100];
struct nod{long long c,d;
int a,b,p;};
nod v[200100];
bool cmp(nod a,nod b)
{
    if(a.c==b.c)
    return  a.d>b.d;
    return a.c<b.c;
}
int tata(int nod)
{
    if(t[nod]==nod)
    {
        return nod;
    }
    t[nod]=tata(t[nod]);
    return t[nod];
}
int main()
{
   f>>n>>m;
   for(i=1;i<=m;++i)
   {
       f>>v[i].a>>v[i].b>>v[i].c>>v[i].d;
       v[i].p=i;
   }
   sort(v+1,v+m+1,cmp);
   for(i=1;i<=n;++i)
   t[i]=i;
   for(i=1;i<=m;++i)
   {
       x=tata(v[i].a);
       y=tata(v[i].b);
       if(x!=y)
       {
           t[y]=x;
           ++nr;
           sol[nr]=v[i].p;
       }
   }
   sort(sol+1,sol+n);
   for(i=1;i<n;++i)
   g<<sol[i]<<'\n';
}