Chillee

ll euclid(ll a, ll b, ll &x, ll &y) {
    if (b) {
        ll d = euclid(b, a % b, y, x);
        return y -= a / b * x, d;
    }
    return x = 1, y = 0, a;
}

Chillee

template <int MAXN> struct Dsu {
    int par[MAXN], sz[MAXN];
    void init(int n) { iota(par, par + n, 0), fill(sz, sz + n, 1); }
    int root(int v) { return v == par[v] ? v : (par[v] = root(par[v])); }

    void merge(int a, int b) {
        if ((a = root(a)) == (b = root(b)))
            return;
        if (sz[a] < sz[b])
            swap(a, b);

Chillee

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

struct chash {
    const int RANDOM = (long long)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
    static unsigned long long hash_f(unsigned long long x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);

Chillee

int N, M;
int bit[MAXN][MAXN];
int sum(int x, int y) {
    int ret = 0;
    for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
        for (int j = y; j >= 0; j = (j & (j + 1)) - 1)
            ret += bit[i][j];
    return ret;
}
void add(int x, int y, int delta) {

Chillee

int F[1 << MAXBITS];
for (int i = 0; i <= MAXBITS; ++i) {
    for (int mask = 0; mask < (1 << MAXBITS); ++mask) {
        if (mask & (1 << i)) {
            F[mask] = max(F[mask], F[mask ^ (1 << i)]);
        }
    }
}

Chillee

template <int MAXV, class T = int> struct Dinic {
    const static bool SCALING = false; // non-scaling = V^2E, Scaling=VElog(U) with higher constant
    int lim = 1;
    const T INF = numeric_limits<T>::max();
    struct edge {
        int to, rev;
        T cap, flow;
    };
    int s = MAXV - 2, t = MAXV - 1;

Chillee

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(seed);

struct node {
    node *l = nullptr, *r = nullptr;
    int val, key = rnd();
    int sz = 1;
    node(int value) : val(value) {}
    ~node() { delete l, delete r; }
    node *upd() {

Chillee

/** Constants Start **/
const double PI = acos(-1.0);
const double EPS = 1e-8;
const double INF = 1e9 + 5;
template <typename T> int sgn(T x) { return x < -EPS ? -1 : x > EPS; }
/** Constants End **/
/** Base Start **/
struct pt {
    T x, y;
    pt operator+(pt p) { return {x + p.x, y + p.y}; }

Chillee

struct MinCostFlow {
    const static int MAXV = MAXN;
    const int INF = 1e9 + 5;
    const int s = MAXV - 2, t = MAXV - 1;
    struct edge {
        int from, to, cap, flow, cost;
    };

    int cost[MAXV][MAXV];
    vector<edge> edges;

Chillee

  struct matrix {
    vector<vector<ll>> cells;

    matrix(vector<vector<ll>> input) : cells(input) {}
    matrix(ll n, ll m, ll val) {
        cells.resize(n);
        vector<ll> row(m);
        fill(row.begin(), row.end(), val);
        fill(cells.begin(), cells.end(), row);
    }