APIO 2020 swap

#include "swap.h"

#include <bits/stdc++.h>
#ifdef local
#define debug(...) qqbx(#__VA_ARGS__, __VA_ARGS__)
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
void qqbx(const char *s) {s;}
template <typename H, typename ...T> void qqbx(const char *s, const H &h, T ...args) {
    for(; *s && *s != ','; ++s) if(*s != ' ') std::cerr << *s;
    std::cerr << " = " << h << (sizeof...(T) ? ", " : "\n");
    if(sizeof...(T)) qqbx(++s, args...);
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define pb emplace_back

using namespace std;
const int N = 400025, inf = 1e9;

vector<tuple<int,int,int>> edges;
int now;
struct PersistentArray {
    vector<pair<int,int>> val[N];
    void init(int n, function<int(int)> gen) {
        for(int i = 0; i < n; i++) val[i].clear();
        for(int i = 0; i < n; i++) add(i, gen(i), -1);
    }
    void add(int p, int d, int t=now) {
        if(val[p].size() && val[p].back().first == t) val[p].back().second = d;
        else val[p].pb(t, d);
    }
    int query(int p, int t=now) {
        if(val[p].back().first <= t) return val[p].back().second;
        return prev(upper_bound(val[p].begin(), val[p].end(), pair<int,int>(t, inf)))->second;
    }
} pa, mx;
int sz[N], deg[N];
int n;
int anc(int x, int t=now, int r=0) {
    int p = pa.query(x, t);
    if(x==p) return x;
    p=anc(p, t, r);
    if(!r) pa.add(x, p, t);
    return p;
}
void join(int x, int y) {
    int dx = ++deg[x], dy = ++deg[y];
    x = anc(x), y = anc(y);
    if(x == y) {
        if(mx.query(x) < 3) mx.add(x, 3);
    } else {
        if(sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y];
        int m = max({ mx.query(y), dx, dy });
        if(mx.query(x) < m) mx.add(x, m);
        pa.add(y, x);
    }
}
bool ok(int t, int x, int y) {
    int ax = anc(x, t, 1);
    int ay = anc(y, t, 1);
    return ax == ay && mx.query(ax, t) >= 3;
}
void init(int _n, int m, vector<int> u, vector<int> v, vector<int> w) {
    n = _n;
    edges.resize(m);
    for(int i = 0; i < m; i++) edges[i] = {w[i], u[i], v[i]};
    sort(edges.begin(), edges.end());
    pa.init(n, [](int x){return x;});
    mx.init(n, [](int x){return 0;});
    safe;
    for(int i = 0; i < n; i++) sz[i] = 1, deg[i] = 0;
    now = 0;
    for(int i = 0; i < m; i++) {
        int a = get<1>(edges[i]), b = get<2>(edges[i]);
        join(a, b);
        now++;
    }
    /*
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            cerr << pa.query(j, i) << ' ';
        }
        cerr<<endl;
        for(int j = 0; j < n; j++) {
            cerr << mx.query(j, i) << ' ';
        }
        cerr<<endl;
    }
    */
}

int getMinimumFuelCapacity(int X, int Y) {
    if(!ok(edges.size(), X, Y)) return -1;
    int p = -1;
    for(int s = 1<<__lg(edges.size()); s; s>>=1) if(p+s < edges.size() && !ok(p+s, X, Y)) p += s;
    debug(p);
    return get<0>(edges[++p]);
    /*
    int res = -1;
    for(int i = 0; i < edges.size(); i++) {
        dsu.join(get<1>(edges[i]), get<2>(edges[i]), true);
        if(dsu.ok(X, Y)) {
            res = get<0>(edges[i]);
            break;
        }
    }
    dsu.undo();
    return res;
    */
}