daily pastebin goal
68%
SHARE
TWEET

Untitled

a guest Dec 16th, 2018 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define fr first
  4.  
  5. #define sc second
  6.  
  7. #define m_p make_pair
  8.  
  9. using namespace std;
  10.  
  11. typedef long long ll;
  12.  
  13. const int INF = 2e9 + 100;
  14.  
  15. const int maxn = 1e3 + 10;
  16.  
  17. struct heap {
  18.     pair<int, int> v;
  19.  
  20.     int deg, id;
  21.  
  22.     heap *ch, *sib, *p;
  23.  
  24.     heap(int v_, int id_, int rid_) :
  25.         v(m_p(v_, id_)), deg(0), id(rid_), ch(nullptr), sib(nullptr), p(nullptr) {}
  26. };
  27.  
  28. typedef heap * ptr;
  29.  
  30. vector<ptr> q;
  31.  
  32. int n;
  33.  
  34. class b_heap {
  35.  public:
  36.     int ind;
  37.     vector<ptr> root;
  38.  
  39.     b_heap() {
  40.         root.resize(22, nullptr);
  41.     }
  42.  
  43.     void merge(b_heap &a) {
  44.         ptr v = nullptr;
  45.         for (int i = 0; i < 22; i++) {
  46.             if (root[i] == nullptr || (a.root[i] != nullptr && a.root[i]->v < root[i]->v))
  47.                 swap(root[i], a.root[i]);
  48.             if (root[i] == nullptr || (v != nullptr && v->v < root[i]->v))
  49.                 swap(root[i], v);
  50.             if (a.root[i] == nullptr || (v != nullptr && v->v < a.root[i]->v))
  51.                 swap(a.root[i], v);
  52.             if (a.root[i] != nullptr) {
  53.                 a.root[i]->sib = root[i]->ch;
  54.                 a.root[i]->p = root[i];
  55.                 root[i]->ch = a.root[i];
  56.                 root[i]->deg++;
  57.                 swap(root[i], v);
  58.                 a.root[i] = nullptr;
  59.             }
  60.             if (root[i] != nullptr)
  61.                 root[i]->id = ind;
  62.         }
  63.     }
  64.  
  65.     int get_min() {
  66.         pair<int, int> ans;
  67.         ans.sc = -1;
  68.         for (auto i : root)
  69.             if (i != nullptr)
  70.                 if (ans.sc == -1 || ans > i->v)
  71.                     ans = i->v;
  72.         return ans.fr;
  73.     }
  74.  
  75.     void extract_min(int id, int val);
  76. };
  77.  
  78. b_heap arr[maxn];
  79.  
  80. void b_heap::extract_min(int id, int val) {
  81.     if (id == -1) {
  82.         pair<int, int> ans;
  83.         ans.sc = -1;
  84.         for (int i = 0; i < (int)root.size(); i++)
  85.             if (root[i] != nullptr)
  86.                 if (ans.sc == -1 || ans > root[i]->v)
  87.                     ans = root[i]->v, id = i;
  88.     }
  89.     if (id == -2) {
  90.         for (int i = 0; i < (int)root.size(); i++)
  91.             if (root[i] != nullptr && root[i]->v.sc == val) {
  92.                 id = i;
  93.                 break;
  94.             }
  95.     }
  96.     int deg = root[id]->deg;
  97.     ptr t = root[id]->ch;
  98.     for (int i = 0; i < deg; i++) {
  99.         t->p = nullptr;
  100.         arr[n].root[deg - 1 - i] = t;
  101.         t = t->sib;
  102.     }
  103.     root[id] = nullptr;
  104.     merge(arr[n]);
  105. }
  106.  
  107. int decrease_key(int id, int w) {
  108.     ptr t = q[id];
  109.     if (t == nullptr)
  110.         return -1;
  111.     t->v.fr = w;
  112.     while (t->p != nullptr && t->p->v >= t->v)
  113.         swap(t->p->v, t->v), q[t->v.sc] = t, q[t->p->v.sc] = t->p, t = t->p;
  114.     while (t->p != nullptr)
  115.         t = t->p;
  116.     return t->id;
  117. }
  118.  
  119. mt19937 rnd(23);
  120.  
  121. int main() {
  122.     #ifdef ONPC
  123.     freopen("a.in", "r", stdin);
  124.     freopen("a.out", "w", stdout);
  125.     #else
  126.     // freopen("priorityqueue2.in", "r", stdin);
  127.     // freopen("priorityqueue2.out", "w", stdout);
  128.     #endif  // ONPC
  129.     ios::sync_with_stdio(0);
  130.     cin.tie(0);
  131.     int m;
  132.     cin >> n >> m;
  133.     for (int i = 0; i <= n; i++)
  134.         arr[i].ind = i;
  135.     while (m--) {
  136.         int ts;
  137.         cin >> ts;
  138.         if (ts == 0) {
  139.             int v, id;
  140.             cin >> id >> v;
  141.             id--;
  142.             arr[n].root[0] = new heap(v, (int)q.size(), n);
  143.             q.push_back(arr[n].root[0]);
  144.             arr[id].merge(arr[n]);
  145.         }
  146.         if (ts == 1) {
  147.             int a, b;
  148.             cin >> a >> b;
  149.             a--;
  150.             b--;
  151.             arr[b].merge(arr[a]);
  152.         }
  153.         if (ts == 2) {
  154.             int id;
  155.             cin >> id;
  156.             id--;
  157.             if (q[id] != nullptr) {
  158.                 int ind = decrease_key(id, INT_MIN);
  159.                 arr[ind].extract_min(-2, id);
  160.             }
  161.         }
  162.         if (ts == 3) {
  163.             int id, v;
  164.             cin >> id >> v;
  165.             id--;
  166.             if (q[id] != nullptr) {
  167.                 int ind = decrease_key(id, INT_MIN);
  168.                 arr[ind].extract_min(-2, id);
  169.                 arr[n].root[0] = new heap(v, id, n);
  170.                 q[id] = arr[n].root[0];
  171.                 arr[ind].merge(arr[n]);
  172.             }
  173.         }
  174.         if (ts == 4) {
  175.             int id;
  176.             cin >> id;
  177.             cout << arr[id - 1].get_min() << '\n';
  178.         }
  179.         if (ts == 5) {
  180.             int id;
  181.             cin >> id;
  182.             arr[id - 1].extract_min(-1, 0);
  183.         }
  184.     }
  185. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top