igorcarpanese

struct Point {
 double x, y;
 Point() : x(0), y(0) {}
 Point(double x, double y) : x(x), y(y) {}
 void read() { scanf("%lf %lf", &x, &y); }
 void print() { printf("(%lf, %lf)\n", x, y); }
};

igorcarpanese

TreapNode* search(TreapNode* &root, int key) {
    if (!root or root->key == key) return root;
    if (root->key < key)  return search(root->right, key);
    if (root->key > key)  return search(root->left, key);
}

igorcarpanese

struct TreapNode {
    // ...

    TreapNode(int key, int priority) {
        this->key = key;
        this->priority = priority;
        this->left = NULL;
        this->right = NULL;
    }
};

igorcarpanese

// Original: https://cp-algorithms.com/data_structures/treap.html#toc-tgt-5
// Time complexity proof: https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap

void heapify(TreapNode *t) {
    if (!t) return;

    TreapNode* max = t;

    if (t->left != NULL  and t->left->priority  > max->priority) max = t->left;
    if (t->right != NULL and t->right->priority > max->priority) max = t->right;

igorcarpanese

bool remove(TreapNode* &root, int key) {
	if (root == NULL) return false;

	if (key < root->key) return remove(root->left, key);
	if (key > root->key) return remove(root->right, key);

    // Case 1: TreapNode to be deleted has no children (it is a leaf TreapNode)
    if (!root->left and !root->right) {
        delete root;
        root = NULL;

igorcarpanese

void right_rotation(TreapNode* &x) {
    TreapNode *y = x->left;
    
    TreapNode *r = y->left; // will not change
    TreapNode *g = y->right;
    TreapNode *b = x->right; // will not change

    x->left = g;
    y->right = x;

igorcarpanese

#include <bits/stdc++.h>
using namespace std;

struct TreapNode {
    int key, priority;
    TreapNode *left, *right;

    TreapNode() {}

    TreapNode(int key) {

igorcarpanese

struct SegmentTree {
    int n;
    vector<int> v;
    vector<int> st;

    SegmentTree(vector<int> &v) : v(v) {
        int n = v.size();
	st.resize(4*n);
        build(0, 0, n);
    }

igorcarpanese

struct CentroidDecomposition {
	vector<set<int>> tree; // it's not vector<vector<int>>!
	vector<int> dad;
	vector<int> sub;

	CentroidDecomposition(vector<set<int>> &tree) : tree(tree) {
		int n = tree.size();
		dad.resize(n);
		sub.resize(n);
		build(0, -1);

igorcarpanese

int dfs(int u, int p) {
    for (auto v : tree[u])
        if (v != p) sub[u] += dfs(v, u);

    return sub[u] + 1;
}

int centroid(int u, int p) {
    for (auto v : tree[u])
        if (v != p and sub[v] > n/2) return centroid(v, u);