Submission #1293749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293749		i_love_kim_ji_won	Klasika (COCI20_klasika)	C++20	0 / 110	5093 ms	50792 KiB

klasika

// I ♡ 김지원
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
using namespace std;

using ll = long long;

void justDoIt();

int main() {
    // freopen("");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    justDoIt();
    return 0;
}

const int N = 2e5 + 5;

const int numnodes = 5e5 + 5;

int st[N], en[N];
vector<int> g[N];
string type[N];
int tin[N], tout[N];
int val[N];

struct Trie {
    struct Node {
        int child[2];
        set<int> s;
    } nodes[numnodes];
    int cur;
    Trie() : cur(0) {
        memset(nodes[0].child, -1, sizeof(nodes[0].child));
        nodes[0].s.clear();
    };
    int new_node() {
        cur++;
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
        nodes[cur].s.clear();
        return cur;
    }
    void add_num(int x, int t) {
        int pos = 0;
        for (int i = 30; i >= 0; i--) {
            int c = (x >> i & 1);
            if (nodes[pos].child[c] == -1) {
                nodes[pos].child[c] = new_node();
            }
            pos = nodes[pos].child[c];
            nodes[pos].s.insert(t);
        }
    }
    int query(int x, int l, int r) {
        int res = 0, pos = 0;
        for (int i = 30; i >= 0; i--) {
            for (int v = 1; v >= 0; v--) {
                int c = (v ^ (x >> i & 1));
                if (nodes[pos].child[c] == -1) {continue;}
                Node t = nodes[nodes[pos].child[c]];
                auto idx = t.s.lower_bound(l);
                if (idx == t.s.end() || *idx > r) {continue;}
                pos = nodes[pos].child[c];
                res += (v << i);
                break;
            }
        }
        return res;
    }
} T;

int timer = 0;
 
void dfs(int u, int p = 0) {
    tin[u] = ++timer;
    for (int v : g[u]) {
        if (v == p) {continue;}
        dfs(v, u);
    }
    tout[u] = timer;
}

void test() {
    int q;
    cin >> q;
    int curr = 1;
    for (int i = 1; i <= q; i++) {
        cin >> type[i] >> st[i] >> en[i];
        if (type[i] == "Add") {
            g[++curr].push_back(st[i]);
            g[st[i]].push_back(curr);
            val[curr] = val[st[i]] ^ en[i];
        }
    }
    dfs(1);
    curr = 1;
    for (int i = 1; i <= q; i++) {
        if (type[i] == "Add") {
            curr++;
            T.add_num(val[curr], tin[curr]);
        }
        else {
            cout << T.query(val[st[i]], tin[en[i]], tout[en[i]]) << '\n';
        }
    }
}

void justDoIt() {
    int t = 1;
    // cin >> t;
    for (int tests = 1; tests <= t; tests++) {
        test();
    }
}

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