Submission #1264851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264851		ceciver	Klasika (COCI20_klasika)	C++20	33 / 110	454 ms	183412 KiB

klasika

/// template {{{
 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <deque>
#include <chrono>
 
#ifdef LOCAL
#include "/Library/debug/debug.h"
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
using namespace std;
 
#define MAX                 2e9
#define MIN                 -2e9
#define by(x)				[](const auto& a, const auto& b) { return a.x < b.x; }
#define INF                 1e14
#define PI                  acos(-1.0)
#define mid(s,e)            (s+(e-s)/2)
#define clz(n)              __builtin_clzll(n)
#define nbofbits(n)         __builtin_popcountll(n)
#define all(x)              (x).begin(), (x).end()
#define endl                '\n'
#define int                 long long
#define pb                  push_back
#define sz(a)               ((int)((a).size()))
#define double              long double
#define fi					first
#define se					second
#define getunique(v)		{sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
 
//const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using pii = pair<int, int>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vpdd = vector<pdd>;
// }}}

struct Trie {
    vvi nxt;
    vi childs;

    Trie() {
        nxt.push_back(vi(2,-1));
    }

    void insert(int x, bool record = true) {
        if(record) childs.pb(x);
        int curr = 0;
        for(int i=30;i>=0;i--) {
            int b = (x >> i) & 1;
            if(nxt[curr][b] == -1) {
                nxt.push_back(vi(2, -1));
                nxt[curr][b] = nxt.size() - 1;
            }
            curr = nxt[curr][b];
        }
    }

    int mx_xor(int x) {
        if (nxt.size() == 1 && nxt[0][0] == -1 && nxt[0][1] == -1) return 0;
        int curr = 0;
        int ans = 0;
        for(int i=30;i>=0;i--) {
            int b = (x >> i) & 1;
            if(nxt[curr][!b] != -1) {
                curr = nxt[curr][!b];
                ans |= (1LL << i);
            }else {
                curr = nxt[curr][b];
            }
        }
        return ans;
    }

};


vvi adj;
vi path_xor;
vi in;
vi out;

void dfs(int i, int& c) {
    c++;
    in[i] = c;
    for(int u: adj[i]) {
        dfs(u, c);
    }
    out[i] = c;
}


void solve() {
    int q; cin>>q;
    vector<array<int,3>> queries(q);
    int edges = 0;

    bool flag = 1;
    for(int i=0;i<q;i++) {
        string type;
        int a, w;
        cin>>type>>a>>w;
        if(type == "Add") edges++;
        if(type == "Query") {
            flag &= w == 1;
        }
        queries[i] = {type == "Add", a - 1, w};
    }

    int n = edges + 1;

    adj = vvi(n);
    path_xor = vi(n);
    in = vi(n);
    out = vi(n);

    {
        int nxt = 1;
        for(auto [t, a, w]: queries) {
            if(t == 0) continue;
            adj[a].pb(nxt);
            path_xor[nxt] = path_xor[a] ^ w;;
            nxt++;
        }
    }

    if(flag) {
        Trie global; global.insert(0);
        int nxt = 1;
        for(auto [t, a, b]: queries) {
            if(t == 1) {
                Trie t;
                t.insert(path_xor[nxt]);
                global.insert(path_xor[nxt]);
                nxt++;
            }else {
                b--;
                if(b == 0) {
                    int ans = global.mx_xor(path_xor[a]);
                    cout<<ans<<endl;
                }
            }

        }
        return;
    }



    {
        int c = -1;
        dfs(0, c);
    }


    /*
    Tree sg(1);
    Trie t;
    t.insert(5);
    cout<<t.mx_xor(0)<<endl;
    sg.update(0, t);
    cout<<sg.query(0, 1).mx_xor(0)<<endl;
    */

    const int B = 5000;
    const int NB = (n + B - 1) / B;

    vector<Trie> t(NB);

    vi vals(n, -1);

    auto upd = [&](int i, int v) {
        vals[i] = v;
        t[i/B].insert(v);
    };

    auto query = [&](int l, int r, int x) {
        int L = (l + B - 1)/ B;
        int R = (r + 1) / B - 1;

        int ans = x ^ vals[l];

        for(int i=L;i<=min(R, NB-1);i++) {
            ans = max(ans, t[i].mx_xor(x));
        }


        for(int i=l;i<min(r+1, B*L);i++) {
            if(vals[i] != -1) 
                ans = max(ans, x ^ vals[i]);
        }

        for(int i=B*(R+1);i<=r;i++) {
            if(vals[i] != -1) 
                ans = max(ans, x ^ vals[i]);
        }

        return ans;
    };



    upd(in[0], 0);

    int nxt = 1;
    for(auto [t, a, b]: queries) {
        if(t == 1) {
            upd(in[nxt], path_xor[nxt]);
            nxt++;
        }else {
            b--;
            int ans = query(in[b], out[b], path_xor[a]);
            cout<<ans<<endl;
        }
    }



}
 
void preprocessing() {
}
 
bool multi_test_cases = 0;
 
// main {{{
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(20);
    cout << fixed;
 
    preprocessing();
 
    int t = 1;
    if (multi_test_cases) cin >> t;
 
    while (t--) {
        solve();
    }
 
    return 0;
}
 
 

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