Cod sursa(job #3229548)

Utilizator SSKMFSS KMF SSKMF Data 16 mai 2024 16:44:54
Problema Heapuri cu reuniune Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <fstream>
using namespace std;

ifstream cin ("mergeheap.in");
ofstream cout ("mergeheap.out");

struct Nod {
    int valoare;
    Nod *frate , *fiu;
    Nod () : valoare(0) , frate(NULL) , fiu(NULL)
        { }
    Nod (const int _valoare) : valoare(_valoare) , frate(NULL) , fiu(NULL)
        { }
} *multime[101];

Nod* Unire (Nod *rezultat , Nod *termen)
{
    if (termen == NULL)
        { return rezultat; }
    if (rezultat == NULL)
        { return (rezultat = termen); }
    if (rezultat -> valoare < termen -> valoare)
        { swap(rezultat , termen); }
    termen -> frate = rezultat -> fiu;
    rezultat -> fiu = termen;
    return rezultat;
}

Nod* toHeap (Nod *nod_actual)
{
    if (nod_actual == NULL || nod_actual -> frate == NULL)
        { return nod_actual; }
    
    Nod *copie = nod_actual -> frate -> frate;
    nod_actual -> frate -> frate = NULL;
    
    return (Unire(toHeap(copie) , Unire(nod_actual , nod_actual -> frate)));
}

int main ()
{
    int numar_operatii;
    for (cin >> numar_operatii >> numar_operatii ; numar_operatii-- ; )
    {
        int8_t tip;
        cin >> tip;

        if (tip == '1')
        {
            int indice , valoare;
            cin >> indice >> valoare;
            Nod *temporar = new Nod(valoare);
            multime[indice] = Unire(multime[indice] , temporar);
        }
        else
            if (tip == '2')
            {
                int indice;
                cin >> indice;
                cout << multime[indice] -> valoare << '\n';

                Nod *anterior = multime[indice];
                multime[indice] = toHeap(multime[indice] -> fiu); 
                delete anterior;
            }
        else
        {
            int indice_1 , indice_2;
            cin >> indice_1 >> indice_2;
            multime[indice_1] = Unire(multime[indice_1] , multime[indice_2]);
        }
    }

    cout.close(); cin.close();
    return 0;
}