Submission #875154

#	Time	Username	Problem	Language	Result	Execution time	Memory
875154		Dr_rabi3	Klasika (COCI20_klasika)	C++14	0 / 110	1517 ms	524292 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 {
    int t, a, b;
};

vector<int>adj[N];
vector<int>in(N), out(N);
vector<query>Q;
int 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<int, 2>> trie;
    vector<array<set<int>, 2>> numsIn;
    vector<array<set<int>, 2>> numsOut;
    int LOG;
    binary_trie(int _LOG) : LOG(_LOG) {
        trie = { array<int, 2>{-1, -1} };
        numsIn = { array<set<int>, 2>{} };
        numsOut = { array<set<int>, 2>{} };
    }

    void insert(int x, int 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]);
                numsOut[v][to].insert(out[u]);
                v = trie[v][to];
            }
            else {
                numsIn[v][to].insert(in[u]);
                numsOut[v][to].insert(out[u]);
                v = (trie[v][to] = (int)trie.size());
                trie.push_back(array<int, 2>{-1, -1});
                numsIn.push_back(array<set<int>, 2>{});
                numsOut.push_back(array<set<int>, 2>{});
            }
        }
    }

    ll query_max(ll x, int u) {
        ll v = 0, sum = 0;
        for (int bit = LOG - 1; bit >= 0; bit--) {
            ll to = ((1LL << bit) & x ? 0 : 1);
            if (~trie[v][to]) {
                auto itIn = numsIn[v][to].lower_bound(in[u]);
                auto itOut = numsOut[v][to].upper_bound(out[u]);
                --itOut;
                // cout << bit << ' ' << *itIn << ' ' << *itOut << ' ' << in[u] << ' ' << out[u] << ed;
                if (itIn != numsIn[v][to].end() and itOut != numsOut[v][to].end()
                    and *itIn >= in[u] and *(--itOut) <= out[u]) {
                    v = trie[v][to], sum += to * (1LL << bit);
                }
                else v = trie[v][1 - to], sum += (1 - 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(32);
    vector<int>preXor(N);
    for (int i = 0;i < q;i++) {
        string s;
        int a, b;
        cin >> s >> a >> b;
        if (s == "Add") {
            adj[a].push_back(++n);
            preXor[n] = preXor[a] ^ b;
            Q.push_back({ 1,a,b });
        }
        else {
            Q.push_back({ 2,a,b });
        }
    }
    dfs(1);
    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 {
            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:151:30: warning: operation on 'n' may be undefined [-Wsequence-point]
  151 |             tr.insert(preXor[++n], n);
      |                              ^~~
klasika.cpp:151:30: warning: operation on 'n' may be undefined [-Wsequence-point]

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