Submission #1101139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101139		InvMOD	Klasika (COCI20_klasika)	C++14	110 / 110	2096 ms	524288 KiB

klasika

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


using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T &a, T b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T &a, T b){if(a > b) return a = b, true; return false;}


const int N = 2e5;
const int C = 2;

struct Query{
    int8_t op;
    int v1, v2;
    Query(int8_t op = 0, int v1 = 0, int v2 = 0): op(op), v1(v1), v2(v2) {}
};
struct Trie{
    struct Node{
        Node* child[C];
        set<int> ckset;

        Node(){
            ckset.insert(N+1);
            for(int i = 0; i < C; i++){
                child[i] = nullptr;
            }
            return;
        }

        bool ck_good(const int& tin, const int& tout){
            return ((*ckset.lower_bound(tin)) <= tout);
        }

        void add(const int& tin){
            return void(ckset.insert(tin));
        }
    };

    typedef Node* pNode;
    pNode root;
    int mxB;
    Trie(int maxBit): mxB(maxBit){
        root = new Node();
    }

    void add_Num(int& x, int& tin){
        pNode cur = root;
        for(int i = mxB; i >= 0; i--){
            int v = (x>>i&1);
            if(cur->child[v] == nullptr){
                cur->child[v] = new Node();
            }
            cur = cur->child[v];
            cur->add(tin);
        }
        return;
    }

    int get_MaxXor(const int& x, const int& tin, const int& tout){
        pNode cur = root;
        int answer = 0;
        for(int i = mxB; i >= 0; i--){
            int v = ((x>>i&1)^1);
            if(cur->child[v] != nullptr && cur->child[v]->ck_good(tin, tout)){
                cur = cur->child[v];
                answer = answer ^ (1<<i);
            }
            else{
                cur = cur->child[(v^1)];
            }
        }
        return answer;
    }
};

int q, i, timerDFS, mx;
vector<int> tin, tout, val;
vector<Query> Q;
vector<vector<int>> adj;

void dfs(int x){
    tin[x] = ++timerDFS;
    for(int v: adj[x]){
        val[v] ^= val[x];
        dfs(v);
    }
    tout[x] = timerDFS;
    return;
}

void solve()
{
    cin >> q;
    timerDFS = 0, mx = 0;
    val.push_back(0);
    adj.push_back(vector<int>());
    for(i = 0; i < q; i++){
        string op;
        cin >> op;
        if(op == "Add"){
            int x,y; cin >> x >> y;
            --x;
            adj[x].push_back(++timerDFS);
            adj.push_back(vector<int>());
            Q.push_back(Query(1, x, timerDFS));
            val.push_back(y);
            mx = max(mx, y);
        }
        else{
            int u,v; cin >> u >> v;
            u--, v--;
            Q.push_back(Query(2, u, v));
        }
    }

    tin.resize(val.size());
    tout.resize(val.size());
    timerDFS = 0;
    dfs(0);

    Trie trie(31 - __builtin_clz(mx));
    trie.add_Num(val[0], tin[0]);
    for(i = 0; i < q; i++){
        if(Q[i].op == 1){
            trie.add_Num(val[Q[i].v2], tin[Q[i].v2]);
        }
        else{
            cout << trie.get_MaxXor(val[Q[i].v1], tin[Q[i].v2], tout[Q[i].v2]) <<"\n";
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44