Cod sursa(job #1917412)

Utilizator EpictetStamatin Cristian Epictet Data 9 martie 2017 12:11:50
Problema Lazy Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

fstream fin ("lazy.in", ios::in), fout ("lazy.out", ios::out);

const double eps = 1e-10;
class Edge { public : int x, y, id; long long c1; double c2; } Muk[200010];
class cmp
{   public :
        bool operator () (const Edge &a, const Edge &b)
        {
            if (a.c1 < b.c1) return true;
            else if (a.c1 == b.c1 && a.c2 - eps > b.c2) return true;
            return false;
        }
};
int n, m, T[200010], R[200010];
vector < int > Sol;

int Find(int node)
{
    int aux, boss = node;
    while (T[boss] != boss) boss = T[boss];
    while (T[node] != node)
    {
        aux = T[node];
        T[node] = boss;
        node = aux;
    }
    return boss;
}

void Unite(int boss1, int boss2)
{
    if (R[boss1] < R[boss2])
    {
        R[boss2] += R[boss1];
        T[boss1] = boss2;
    }
    else
    {
        R[boss1] += R[boss2];
        T[boss2] = boss1;
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        long long cc22, semn;
        fin >> Muk[i].x >> Muk[i].y >> Muk[i].c1 >> cc22;
        Muk[i].c2 = log2(Muk[i].c1) + (cc22 < 0 ? -log2(-cc22) : log2(cc22));
        Muk[i].id = i;
    }
    sort(Muk + 1, Muk + 1 + m, cmp());
    for (int i = 1; i <= n; i ++)
    {
        R[i] = 1;
        T[i] = i;
    }
    for (int i = 1; i <= m; i ++)
    {
        int b1 = Find(Muk[i].x);
        int b2 = Find(Muk[i].y);
        if (b1 != b2)
        {
            Unite(b1, b2);
            Sol.push_back(Muk[i].id);
        }
    }
    for (auto it : Sol) fout << it << '\n';
    fin.close();
    fout.close();
    return 0;
}