Submission #736135

#	Time	Username	Problem	Language	Result	Execution time	Memory
736135		marvinthang	Klasika (COCI20_klasika)	C++17	110 / 110	2329 ms	439752 KiB

klasika

/******************************
*    author : @marvinthang    *
*    date : 17 / 11 / 2021    *
******************************/

#include <bits/stdc++.h>

using namespace std;

#define  superspeed  ios_base::sync_with_stdio(false);\
                     cin.tie(NULL);\
                     //cout.tie(NULL);
#define  file(name)  freopen(name".inp", "r", stdin);\
                     freopen(name".out", "w", stdout);

const       int MOD = 1e9 + 7; // 998244353;
const     double PI = 3.1415926535897932384626433832795; // acos((db)-1); atan(-1.0);
const      int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const  long long oo = 1e18;
const       int MAX = 2e5 + 5;

int Q, N = 1, in[MAX], out[MAX], timeDfs, dist[MAX], A[MAX], B[MAX];
vector <pair <int, int>> adj[MAX];
string type[MAX];

void dfs(int u, int par) {
    in[u] = ++timeDfs;
    for (auto &x: adj[u]) {
        int v = x.second;
        int w = x.first;
        if (v == par) continue;
        dist[v] = dist[u] ^ w;
        dfs(v, u);
    }
    out[u] = timeDfs;
}

struct TrieNode {
    TrieNode *child[2];
    set <int> s;
    TrieNode() {
        child[0] = child[1] = nullptr;
        s.clear();
    }
};
const int LOG = 31;

TrieNode *root = new TrieNode();

void TrieInsert(int val, int pos) {
    TrieNode *p = root;
    for (int i = LOG - 1; i >= 0; --i) {
        int bit = (val >> i) & 1;
        if (p -> child[bit] == nullptr) p -> child[bit] = new TrieNode();
        p = p -> child[bit];
        p -> s.insert(pos);
    }
}

int TrieMaxXOR(int val, int l, int r) {
    TrieNode *p = root;
    int res = 0;
    for (int i = LOG - 1; i >= 0; --i) {
        int bit = (val >> i) & 1;
        if (p -> child[bit ^ 1] != nullptr) {
            set <int> :: iterator x = p -> child[bit ^ 1] -> s.lower_bound(l);
            if (*x <= r && x != p -> child[bit ^ 1] -> s.end()) {
                p = p -> child[bit ^ 1];
                res |= (1 << i);
            } else p = p -> child[bit];
        } else p = p -> child[bit];
    }
    return res;
}

int main() {
    superspeed
    cin >> Q;
    for (int i = 1; i <= Q; ++i) {
        cin >> type[i] >> A[i] >> B[i];
        if (type[i] == "Add") {
            int u = A[i];
            int v = ++N;
            int w = B[i];
            A[i] = v;
            adj[u].push_back({w, v});
            adj[v].push_back({w, u});
        }
    }
    dfs(1, 0);
    TrieInsert(dist[1], in[1]);
    for (int i = 1; i <= Q; ++i) {
        if (type[i] == "Add") {
            TrieInsert(dist[A[i]], in[A[i]]);
        } else {
            cout << TrieMaxXOR(dist[A[i]], in[B[i]], out[B[i]]) << '\n';
        }
    }
    return 0;
}

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