Regional 2022 Day2 E. DSU

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int long long
#define mp make_pair
#define pb push_back

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

constexpr int N = (int)3e3+11;
constexpr int INF = (int)1e18;

template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rnd(time(nullptr));

struct DSU{
    vector<int> p;
    vector<ordered_set<int>> vt;
    int sz;
    DSU(){}
    DSU(int n){
        sz = n + 1;
        p.resize(sz);
        vt.resize(sz);
        for(int i = 0; i < sz; i++)
            p[i] = i, vt[i].insert(i);
    }
    int get(int x){
        if(p[x] == x)
            return x;
        return p[x] = get(p[x]);
    }
    void union_sets(int a,int b){
        a = get(a), b = get(b);
        if(a == b)
            return;
        if(vt[a].size() > vt[b].size())
            swap(a,b);
        p[a] = b;
        for(auto& x : vt[a])
            vt[b].insert(x);
        return;
    }
    int answer(int v,int k){
        v = get(v);
        if(vt[v].size() < k)
            return -1;
        return *vt[v].find_by_order(k-1);
    }
};

map<int,DSU> d;

int n,q,group;
vector<pair<int,pair<int,int>>> Q;

DSU get(int x){
    DSU cur(n);
//    cerr << "x = " << x << "\n";
    int i = 1;
    for(int i = 1; i <= x; i++){
        int tp;
        tp = Q[i-1].first;
        if(tp == 2){
            int a,b;
            a = Q[i-1].second.first, b = Q[i-1].second.second;
            cur.union_sets(a,b);
        }
        if(tp == 3){
            int t;
            t = Q[i-1].second.first;
            cur = get(t);
        }
    }
//    cerr << "??? " << cur.get(1) << "\n";
    return cur;
}

void solve(){
    cin >> n >> q >> group;
    DSU cur(n);
    d[0] = cur;
    /// LETS MAKE IT OFFLINE
    set<int> QQ;
    for(int i = 0; i < q; i++){
        int tp;
        cin >> tp;
        if(tp == 1){
            int v,k;
            cin >> v >> k;
            Q.pb(mp(1,mp(v,k)));
//            cout << cur.answer(v,k) << "\n";
        }
        if(tp == 2){
            int a,b;
            cin >> a >> b;
            Q.pb(mp(2,mp(a,b)));
//            cur.union_sets(a,b);
        }
        if(tp == 3){
            int x;
            cin >> x;
            Q.pb(mp(3,mp(x,-1)));
            QQ.insert(x);
//            cur = d[x];
        }

    }

    for(int i = 1; i <= q; i++){
        int tp;
        tp = Q[i-1].first;
        if(tp == 1){
            int v,k;
            v = Q[i-1].second.first, k = Q[i-1].second.second;
            cout << cur.answer(v,k) << "\n";
        }
        if(tp == 2){
            int a,b;
            a = Q[i-1].second.first, b = Q[i-1].second.second;
            cur.union_sets(a,b);
        }
        if(tp == 3){
            int x;
            x = Q[i-1].second.first;
            if(group == 7)
                cur = get(x);
            else
                cur = d[x];
        }
        if((group == 0 || group == 3 || group == 6) && QQ.count(i))
            d[i] = cur;
//        cerr << cur.get(1) << "\n";
    }

    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);

    int tests = 1;
    for(int test = 1; test <= tests; test++){
        solve();
    }

    return 0;
}