Cod sursa(job #2742880)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 22 aprilie 2021 09:45:19
Problema Heapuri cu reuniune Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.14 kb
#include <bits/stdc++.h>

using namespace std;

FILE *f = fopen("mergeheap.in","r");
FILE *g = fopen("mergeheap.out","w");

const int LGMAX = 19;

class FibonacciHeap{
    struct node_t{
        int key;
        node_t* nxt;
        node_t* ant;
        vector<node_t*> sons;

        node_t(int x){
            key = x;
            nxt = this;
            ant = this;
            sons = vector<node_t*>();
        }
    };

    node_t* nill;
    node_t* max_ptr;

public:

    FibonacciHeap(){
        nill = new node_t(-(2e9 + 5));
        max_ptr = nill;
    }
   
    void insert(int x){
        node_t* tmp = new node_t(x);
        tmp->nxt = nill->nxt;
        tmp->ant = nill;
        tmp->nxt->ant = tmp;
        tmp->ant->nxt = tmp;
        if(x > max_ptr->key){
            max_ptr = tmp;
        }
    }

    void merge(const FibonacciHeap &other){
        node_t* fst = nill;
        node_t* lst = nill->ant;
        node_t* fst2 = other.nill->nxt;
        node_t* lst2 = other.nill->ant;
        if(fst2 == other.nill || lst2 == other.nill){
            return;
        }
        lst->nxt = fst2;fst2->ant = lst;
        lst2->nxt = fst;fst->ant = lst2;
        if(this->max_ptr->key < other.max_ptr->key){
            max_ptr = other.max_ptr;
        }
    }

    int get_max(){
        return max_ptr->key;
    }

    void delete_max(){
     
        node_t* lst = max_ptr->ant;

        for(auto &it:max_ptr->sons){
            lst->nxt = it;
            it->ant = lst;
            lst = it;
        }
        lst->nxt = max_ptr->nxt;
        lst->nxt->ant = lst;
        
        vector<node_t*> available_with_deg(LGMAX,NULL);

        for(node_t* it = nill->nxt;it != nill;it = it->nxt){
            node_t* curr = it;
            while(available_with_deg[curr->sons.size()] != NULL){
                node_t* other = available_with_deg[curr->sons.size()];
                if(other->key > curr->key){
                    swap(curr,other);
                }
                available_with_deg[curr->sons.size()] = NULL;
                curr->sons.push_back(other);
            }
            available_with_deg[curr->sons.size()] = curr;
        }
        
        nill->ant = nill;
        nill->nxt = nill;
        max_ptr = lst = nill;

        for(auto &it:available_with_deg){
            if(it != NULL){
                lst->nxt = it;
                it->ant = lst;
                lst = it;
                if(max_ptr->key < it->key){
                    max_ptr = it;
                }
            }
        }

        lst->nxt = nill;
        nill->ant = lst;
    }
};

int n,q;
FibonacciHeap v[105];

int main(){

    fscanf(f,"%d %d",&n,&q);

    for(int i = 1;i <= q;i++){
        int t;
        fscanf(f,"%d",&t);

        if(t == 1){
            int m,x;
            fscanf(f,"%d %d",&m,&x);
            v[m].insert(x);
        }else if(t == 2){
            int m;
            fscanf(f,"%d",&m);
            fprintf(g,"%d\n",v[m].get_max());
            v[m].delete_max();
        }else{
            int a,b;
            fscanf(f,"%d %d",&a,&b);
            v[a].merge(v[b]);
            v[b] = FibonacciHeap();
        }
    }
    
    
    fclose(f);
    fclose(g);


    return 0;
}