Submission #875158

#	Time	Username	Problem	Language	Result	Execution time	Memory
875158		Dr_rabi3	Klasika (COCI20_klasika)	C++14	33 / 110	1941 ms	524288 KiB

klasika

/***   Coding for Fun ^^ وَمَا تَوْفِيقِي إِلَّا بِاللَّهِ ۚ عَلَيْهِ تَوَكَّلْتُ وَإِلَيْهِ أُنِيبُ    ***/
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/numeric>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ull unsigned ll
#define ld long double
#define ed '\n'
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fixed(x) fixed<<setprecision(x)
#define memo(dp,x) memset(dp,x,sizeof(dp))
#define sumOf(a) (ll)((-1 + sqrt(8LL * a + 1)) / 2)
#define debug cerr
#define Good_Bay return

using namespace std;
using namespace __gnu_pbds;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

template < typename T > using ordered_set = tree< T, null_type, less_equal< T >, rb_tree_tag, tree_order_statistics_node_update >;

template < typename T > istream& operator >> (istream& in, vector < T >& v) {
    for (auto& x : v) in >> x;
    return in;
}

template < typename T > ostream& operator << (ostream& out, const vector < T >& v) {
    for (const T& x : v) out << x << ' ';
    return out;
}


void Accept() { // for VS code
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #else
        // freopen("darwin.in", "r", stdin);
        // freopen("visitfj.out", "w", stdout);
    // #endif
}

constexpr int mod = 1e9 + 7, oo = 0x3f3f3f3f, N = 2e5 + 5;
const double pi = acos(-1), EPS = 1e-7;
constexpr ll OO = 0x3f3f3f3f3f3f3f3f;

constexpr int dy[] = { 0 , 1 , -1 , 0  , 1 , -1 , 1  , -1 };
constexpr int dx[] = { 1 , 0 ,  0 , -1 , 1 , -1 , -1 ,  1 };

struct query {
    ll t, a, b;
    query(int t, int a, int b) : t(t), a(a), b(b) {}
};

vector<ll>adj[N];
vector<ll>in(N), out(N);
vector<query>Q;
ll n = 1, id = 1;

void dfs(int u) {
    in[u] = id++;
    for (auto& v : adj[u]) dfs(v);
    out[u] = id++;
}

struct binary_trie {
    vector<array<ll, 2>> trie;
    vector<array<set<ll>, 2>> numsIn;
    int LOG;
    binary_trie(int _LOG) : LOG(_LOG) {
        trie = { array<ll, 2>{-1, -1} };
        numsIn = { array<set<ll>, 2>{} };
    }

    void insert(ll x, ll u) {
        int v = 0;
        for (int bit = LOG - 1; bit >= 0; --bit) {
            int to = ((1LL << bit) & x ? 1 : 0);
            if (~trie[v][to]) {
                numsIn[v][to].insert(in[u]);
                v = trie[v][to];
            }
            else {
                numsIn[v][to].insert(in[u]);
                v = (trie[v][to] = (int)trie.size());
                trie.push_back(array<ll, 2>{-1, -1});
                numsIn.push_back(array<set<ll>, 2>{});
            }
        }
    }

    ll query_max(ll x, ll u) {
        ll v = 0, sum = 0;
        for (int bit = LOG - 1; bit >= 0; bit--) {
            ll to = ((1LL << bit) & x ? 0 : 1);
            auto itIn = numsIn[v][to].lower_bound(in[u]);
            if (~trie[v][to] and itIn != numsIn[v][to].end() and *itIn <= out[u]) {
                v = trie[v][to], sum += to * (1LL << bit);
            }
            else {
                v = trie[v][1 - to], sum += (1 - to) * (1LL << bit);
            }
        }
        return x ^ sum;
    }
};


void doWork(int T) {
    int q;
    cin >> q;
    binary_trie tr(64);
    for (int i = 0;i < q;i++) {
        string s;
        ll a, b;
        cin >> s >> a >> b;
        if (s == "Add") {
            adj[a].push_back(++n);
            Q.push_back({ 1,a,b });
        }
        else {
            Q.push_back({ 2,a,b });
        }
    }
    dfs(1);
    vector<ll>preXor(n + 1);
    preXor[1] = 0;
    n = 1;
    tr.insert(0, 1);
    for (auto i : Q) {
        if (i.t == 2) cout << tr.query_max(preXor[i.a], i.b) << ed;
        else {
            preXor[++n] = preXor[i.a] ^ i.b;
            tr.insert(preXor[n], n);
        }
    }
}

int main() {
    // debug << "M3L4 El-Code MYTFHM4";
    Accept();
    int _ = 1;
    // cin >> _;
    for (int __ = 1;__ <= _;__++) {
        // cout << "Case " << __ << ": ";
        doWork(__);
        if (__ < _)cout << '\n';
        // cout << '\n';
    }
    Good_Bay 0;
}

Compilation message (stderr)

klasika.cpp: In function 'void doWork(int)':
klasika.cpp:126:29: warning: narrowing conversion of 'a' from 'long long int' to 'int' [-Wnarrowing]
  126 |             Q.push_back({ 1,a,b });
      |                             ^
klasika.cpp:126:31: warning: narrowing conversion of 'b' from 'long long int' to 'int' [-Wnarrowing]
  126 |             Q.push_back({ 1,a,b });
      |                               ^
klasika.cpp:129:29: warning: narrowing conversion of 'a' from 'long long int' to 'int' [-Wnarrowing]
  129 |             Q.push_back({ 2,a,b });
      |                             ^
klasika.cpp:129:31: warning: narrowing conversion of 'b' from 'long long int' to 'int' [-Wnarrowing]
  129 |             Q.push_back({ 2,a,b });
      |                               ^

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