Cod sursa(job #2743095)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 22 aprilie 2021 15:58:31
Problema Heapuri cu reuniune Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <cstdio>

using namespace std;

class Heap{
    struct node_t{
        node_t* child;
        node_t* sibling;
        int key;

        node_t(int key){
            child = NULL;
            sibling = NULL;
            this->key = key;
        }
    }*root;

public:

    Heap(){
        root = NULL;
    }

    node_t* meld(node_t* a,node_t* b){
        if(a == NULL){
            return b;
        }
        if(b == NULL){
            return a;
        }
        if(a->key > b->key){
            b->sibling = a->child;
            a->child = b;
            return a;
        }else{
            a->sibling = b->child;
            b->child = a;
            return b;
        }
    }

    void push(int key){
        node_t *tmp = new node_t(key);
        root = meld(root,tmp);
    }

    int top(){
        return root->key;
    }

    node_t* merge_root_sons(){
        if(root->child == NULL){
            return NULL;
        }
        node_t* a = root->child;
        if(a->sibling == NULL){
            return a;
        }
        node_t* b = a->sibling;
        root->child = b->sibling;
        a->sibling = b->sibling = NULL;
        return meld(meld(a,b),merge_root_sons());
    }

    void pop(){
        root = merge_root_sons();
    }

    void merge(Heap &other){
        root = meld(root,other.root);
    }
}heaps[105];

int n,m;
int t;
int x,y;

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

int main(){

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

    for(int i = 1;i <= n;i++){
        heaps[i] = Heap();
    }

    for(int i = 1;i <= m;i++){
        fscanf(f,"%d",&t);
        if(t == 1){
            fscanf(f,"%d %d",&x,&y);
            heaps[x].push(y);
        }else if(t == 2){
            fscanf(f,"%d",&x);
            fprintf(g,"%d\n",heaps[x].top());
            heaps[x].pop();
        }else{
            fscanf(f,"%d %d",&x,&y);
            heaps[x].merge(heaps[y]);
            heaps[y] = Heap();
        }
    }

    fclose(f);
    fclose(g);

    return 0;
}