Submission #494026

#	Time	Username	Problem	Language	Result	Execution time	Memory
494026		Victor	Klasika (COCI20_klasika)	C++17	33 / 110	2240 ms	524292 KiB

klasika

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;
const int MAXN = 200001;

int xor_root[MAXN + 5], euler_id[MAXN + 5], sub_size[MAXN + 5], n = 1, cnt = 0;

struct Node {
    Node *zero = 0, *one = 0;
    set<int> nodes;
    int node_val = 0;

    void add(int val, int pos, int u) {
        nodes.insert(euler_id[u]);
        if (pos == -1) return;

        if (val & (1 << pos)) {
            if (one == 0) {
                one = new Node;
                one->node_val = node_val | (1 << pos);
                one->nodes.insert(INF);
            }
            one->add(val, pos - 1, u);

        } else {
            if (zero == 0) {
                zero = new Node;
                zero->node_val = node_val;
                zero->nodes.insert(INF);
            }
            zero->add(val, pos - 1, u);
        }
    }

    int query(int val, int pos, int u) {
        if (pos == -1) return node_val;

        bool has_zero = 0;
        if (zero && *zero->nodes.lower_bound(euler_id[u]) < euler_id[u] + sub_size[u]) has_zero = 1;
        bool has_one = 0;
        if (one && *one->nodes.lower_bound(euler_id[u]) < euler_id[u] + sub_size[u]) has_one = 1;

        //cout<<"val = "<<val<<" pos = "<<pos<<" u = "<<u<<" has_zero = "<<has_zero<<" has_one = "<<has_one<<" node_val = "<<node_val<<endl;

        if (!has_zero) return one->query(val, pos - 1, u);
        if (!has_one) return zero->query(val, pos - 1, u);

        if (val & (1 << pos))
            return zero->query(val, pos - 1, u);
        else
            return one->query(val, pos - 1, u);
    }
};

vii graph[MAXN + 5];

void dfs(int u, int cur_xor) {
    sub_size[u] = 1;
    euler_id[u] = cnt++;
    xor_root[u] = cur_xor;

    trav(edge, graph[u]) {
        int v, w;
        tie(v, w) = edge;
        dfs(v, cur_xor ^ w);
        sub_size[u] += sub_size[v];
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    vector<iii> queries;
    int q;

    cin >> q;
    rep(i, 0, q) {
        string type;
        int a, b;
        cin >> type >> a >> b;
        queries.pb({type == "Add", {a, b}});
        if (type == "Add") graph[a - 1].emplace_back(n++, b);
    }

    dfs(0, 0);

    const int len = 30;
    Node trie;
    trie.add(0, len, 0);

    cnt = 1;
    rep(i, 0, q) {
        int type;
        type = queries[i].first;
        if (type) {
            int u, w;
            tie(u, w) = queries[i].second;
            trie.add(xor_root[cnt], len, cnt);
            ++cnt;

        } else {
            int u, v;
            tie(u, v) = queries[i].second;
            cout << (xor_root[u - 1] ^ trie.query(xor_root[u - 1], len, v - 1)) << endl;
        }
    }
    return 0;
}

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