Pagini recente » Cod sursa (job #97003) | Cod sursa (job #566750) | Cod sursa (job #2338575) | Cod sursa (job #2773468) | Cod sursa (job #3126254)
#include <iostream>
#include <vector>
#include <fstream>
#include <unordered_map>
using namespace std;
struct nod{
int key;
nod *left = nullptr, *right = nullptr;
int rrank;
};
class rheap{
nod* root = nullptr;
/*nod* amerge(nod* a, nod *b){
if(a == nullptr)
return b;
if(b == nullptr)
return b;
if(a -> key > b -> key)
swap(a, b);
b -> right = a -> left;
a -> left = b;
b -> parent = a;
a -> right = nullptr;
a -> rank++;
return a;
}*/
public:
rheap(){
}
~rheap(){
}
nod* getroot()const{
return root;
}
void setnroot(){
root = nullptr;
}
static nod* snmerge(nod* a, nod* b){
if(a == nullptr)
return a;
if(b == nullptr)
return b;
if(a -> key < b -> key){
b -> right = a -> left;
a -> left = b;
a -> key++;
return a;
}
else{
a -> right = b -> left;
b -> left = a;
b -> key++;
return b;
}
}
void nmerge(nod* b){
if(root == nullptr){
root = b;
return;
}
if(b == nullptr)
return;
if(root -> key < b -> key){
b -> right = root -> left;
root -> left = b;
root -> rrank++;
}
else{
root -> right = b -> left;
b -> left = root;
b -> rrank++;
root = b;
}
}
int npop(){
int afr = root -> key;
unordered_map<int, vector<nod*>> rmap;
nod* aux = root -> left;
int mrank = -1;
while(aux != nullptr){
rmap[aux->rrank].push_back(aux);
mrank = max(mrank, aux -> rrank);
aux = aux -> right;
}
while(rmap.size() > 1){
nod* a1, *a2, *a3;
a1 = nullptr;
a2 = nullptr;
a3 = nullptr;
for(int i = 0; i <= mrank; i++){
for(int j = 0; j < rmap[i].size(); j++){
if(a1 == nullptr){
a1 = rmap[i][j];
rmap[i].erase(rmap[i].begin() + j);
j--;
}
else if(a2 == nullptr){
a2 = rmap[i][j];
rmap[i].erase(rmap[i].begin() + j);
j--;
a3 = rheap::snmerge(a1, a2);
rmap[a3 -> rrank].push_back(a3);
mrank = max(mrank, a3 -> rrank);
a1 = nullptr;
a2 = nullptr;
}
}
}
}
for(int i = 0; i <= mrank; i++){
if(rmap[i].size() == 1){
root = rmap[i][0];
}
}
return afr;
}
void npush(int val){
nod *aux = new nod;
aux -> key = val;
aux -> rrank = 0;
this -> nmerge(aux);
}
};
int main()
{
int n, q, op;
rheap prnc[105];
ifstream f("mergeheap.in");
ofstream g("mergeheap.out");
int m, x, a, b;
f >> n >> q;
while(q){
f >> op;
//cout << op <<"\n";
switch(op){
case 1:
//cout << "!";
f >> m >> x;
x = x * (-1);
prnc[m].npush(x);
//cout << "!";
break;
case 2:
//cout << "@";
f >> m;
//g << prnc[m].get_min() << "\n";
g << (-1) * prnc[m].npop() << "\n";
//cout << "@";
break;
case 3:
//cout << "#";
f>> a >> b;
prnc[a].nmerge(prnc[b].getroot());
prnc[b].setnroot();
//cout << "#";
break;
}
///DEBUG
/*
cout << "\n\n";
for(int i = 1; i <= n; i++){
cout << i << "\n\n";
nod* aux = prnc[i].getroot();
if(aux != nullptr)
while(aux){
nod *aux2 = aux;
while(aux){
cout << aux -> key << " ";
aux = aux -> right;
}
cout << "\n----\n";
aux = aux2 -> left;
}
else
cout << "NONE";
cout << "\n\n";
}
cout<<"\n\n";
*/
///
q--;
}
}