Submission #857119

#	Time	Username	Problem	Language	Result	Execution time	Memory
857119		Jethro	Klasika (COCI20_klasika)	C++17	33 / 110	1152 ms	524288 KiB

klasika

//Writed by: Jethro_
//----------------------
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

const int N = 3e6 + 10;
int n, node = 1, i, root, val, in[N], out[N], cnt = 0, Xor[N], LG = 31, cnt2 = 0;
vector<pair<int, int>> a[N];
pair<int, int> query[N];
string type[N];

void add() {
    cin >> n;
    for(i = 1; i <= n; ++i) {
        cin >> type[i];
        if(type[i] == "Add") {
            cin >> root >> val;
            a[++node].push_back({root, val});
            a[root].push_back({node, val});
            
            query[i] = {node, node};
            
        }else {
            cin >> root >> val;
            query[i] = {root, val};
        }
    }
}
void dfs(int u, int p) {
    in[u] = ++cnt;
    for(auto [v, w] : a[u]) {
        if(v == p) continue;
        Xor[v] = Xor[u] ^ w;
        dfs(v, u);
    }

    out[u] = cnt;
}
struct Trie{
    struct Node{
        Node* child[2];
        int exist, cnt;
        set<int> save;

        Node() {
            for (int i = 0; i < 2; i++) child[i] = NULL;
            exist = cnt = 0;
        }
    };
 
    int cur;
    Node* root;
    Trie() : cur(0) {
        root = new Node();
    };
    void ADD(int s, int id) {
        Node* p = root;
        int u = 0;

        for(int i = LG; i >= 0; --i) {
            int k = (s >> i) & 1;
            if(p->child[k] == NULL) {
                p->child[k] = new Node();
            }
            p = p->child[k];
            p->save.insert(in[id]);
        }
    }
    int get(int s, int l, int r) {
        int u = 0, res = 0;
        Node* p = root;
        for(int i = LG; i >= 0; --i) {
            int k = (s >> i) & 1;
            if(p->child[k ^ 1] != NULL){
                auto x = p->child[k ^ 1]->save.lower_bound(l);
                if(x != p->child[k ^ 1]->save.end() && (*x) <= r){
                    p = p->child[k ^ 1];
                    res += (1 << i);
                }else {
                    p = p->child[k];
                }
            }else {
                p = p->child[k];
            }
        }
       return res;
    }
} trie;
void solve() {

    dfs(1, 0);
    trie.ADD(0, 1);
    
    for(i = 1; i <= n; ++i) {
        auto [x, y] = query[i];
        if(type[i] == "Add") {
            trie.ADD(Xor[x], y);
        }else {
            int now = Xor[x];
            cout << trie.get(now, in[y], out[y]) << '\n';
        }
    }
}
int main() {

    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    add();
    solve();

}

Compilation message (stderr)

klasika.cpp: In member function 'void Trie::ADD(int, int)':
klasika.cpp:61:13: warning: unused variable 'u' [-Wunused-variable]
   61 |         int u = 0;
      |             ^
klasika.cpp: In member function 'int Trie::get(int, int, int)':
klasika.cpp:73:13: warning: unused variable 'u' [-Wunused-variable]
   73 |         int u = 0, res = 0;
      |             ^

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