Cod sursa(job #2461205)

Utilizator stefantagaTaga Stefan stefantaga Data 25 septembrie 2019 08:23:51
Problema Lazy Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("lazy.in");
ofstream g("lazy.out");
struct wow
{
    int a,b,c1,c2,poz;
}v[200005];
int repr[200005],sol[200005],q,i,n,m;
bool compare (wow a,wow b)
{
    return a.c1<b.c1||(a.c1==b.c1&&a.c2>b.c2);
}
int tatic(int x)
{
    if (repr[x]!=x)
    {
        x=tatic(repr[x]);
    }
    return repr[x];
}
int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>v[i].a>>v[i].b>>v[i].c1>>v[i].c2;
        v[i].poz=i;
    }
    sort (v+1,v+m+1,compare);
    for (i=1;i<=n;i++)
    {
        repr[i]=i;
    }
    for (i=1;i<=m;i++)
    {
        if (tatic(v[i].a)==tatic(v[i].b))
        {
            continue;
        }
        repr[tatic(v[i].a)]=tatic(v[i].b);
        sol[++q]=v[i].poz;
    }
    for (i=1;i<=q;i++)
    {
        g<<sol[i]<<'\n';
    }
    return 0;
}