Submission #965551

#	Time	Username	Problem	Language	Result	Execution time	Memory
965551		dosts	Klasika (COCI20_klasika)	C++17	110 / 110	2099 ms	436600 KiB

klasika

//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int N = 2e5+100,inf = 2e9,MOD = 1e9+7,B = 30;


struct Trie {
    Trie* children[2] = {NULL,NULL};
    set<int> bas;
    void insert(int x,int p) {
        Trie* cur = this;
        for (int i=30;i>=-1;i--) {
            cur->bas.insert(p);
            if (i > -1) {
                bool go = x&(1<<i);
                if (!cur->children[go]) cur->children[go] = new Trie;
                cur = cur->children[go];
            }
        }
    }

    int query(int x,int l,int r) {
        if (bas.empty()) return -inf;
        Trie* cur = this;
        int ans = 0;
        for (int i=30;i>=0;i--) {
            bool go = !(x&(1<<i));
            if (cur->children[go]) {
                auto it = cur->children[go]->bas.lower_bound(l);
                if (it != cur->children[go]->bas.end()) {
                    if (*it <= r) {
                        ans+=(1<<i);
                        cur = cur->children[go];
                        continue;
                    }
                }
            } 
            if (!cur->children[!go]) cur->children[!go] = new Trie;
            cur = cur->children[!go];
        }
        return ans;
    }

};


vi tin(N),tout(N),d(N),edges[N];
int timer = 1;
void dfs(int node) {
    tin[node] = timer++;
    for (auto it : edges[node]) dfs(it);
    tout[node] = timer-1;
}

void solve() {
    d[1] = 0;
    int curnode = 1;
    int q;
    cin >> q;
    vector<pair<int,pii>> qs(q+1);
    for (int i=1;i<=q;i++) {
        string s;
        cin >> s;
        int node,v;
        cin >> node >> v;
        if (s == "Add") {
            edges[node].push_back(++curnode);
            d[curnode] = d[node]^v; 
        }
        qs[i] = (pair<int,pii>{(s != "Add"), pii{node,v}});
    }
    dfs(1);
    Trie* root = new Trie;
    root->insert(0,1);
    int curry = 1;
    for (int i=1;i<=q;i++) {
        int type = qs[i].ff;
        if (!type) {
            ++curry;
            root->insert(d[curry],tin[curry]);
        }
        else {
            auto [a,b] = qs[i].ss;
            cout << root->query(d[a],tin[b],tout[b]) << '\n';
        }
    }
}
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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