Cod sursa(job #1795077)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 1 noiembrie 2016 23:03:17
Problema Lazy Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("lazy.in");
ofstream g("lazy.out");
struct pt
{
    int a,b,poz;
    long long c,c_;
}v[1<<18];
int i,n,m,p,p_,GR[1<<18];
bool cmp(pt a,pt b)
{
    if(a.c==b.c) return a.c_>b.c_;
    return a.c<b.c;
}
int gr(int a)
{
    if(GR[a]!=a) GR[a]=gr(GR[a]);
    return GR[a];
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>v[i].a>>v[i].b>>v[i].c>>v[i].c_;
        v[i].poz=i;
        GR[v[i].a]=v[i].a;
        GR[v[i].b]=v[i].b;
    }
    sort(v+1,v+1+m,cmp);
    for(i=1;i<=m;i++)
    {
        p=gr(v[i].a);
        p_=gr(v[i].b);
        if(p!=p_)
        {
            GR[p_]=p;
            g<<v[i].poz<<'\n';
        }
    }
    return 0;
}