Submission #768406

#	Time	Username	Problem	Language	Result	Execution time	Memory
768406		DylanSmith	Klasika (COCI20_klasika)	C++17	33 / 110	778 ms	524288 KiB

klasika

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#define lb(x,y) lower_bound(all(x),y)-begin(x)
 
mt19937 rng;

typedef struct Node {
    int adj[2], par; bool end;
    Node(int p = -1) {
        end = 0; par = p;
        fill(adj, adj + 2, -1);
    }
} node;

int add(vector<node> &tree, int n) {
    int cur = 0;
    for (int i = 29; i >= 0; i--) {
        if ((n & 1 << i) == 0) {
            if (tree[cur].adj[0] == -1) {
                tree[cur].adj[0] = sz(tree);
                tree.emplace_back(cur);
            }
            cur = tree[cur].adj[0];
        } else {
            if (tree[cur].adj[1] == -1) {
                tree[cur].adj[1] = sz(tree);
                tree.emplace_back(cur);
            }
            cur = tree[cur].adj[1];
        }
    }
    tree[cur].end = true;
    return cur;
}

int maxXor(vector<node> &tree, int n) {
    int cur = 0, res = 0;
    for (int i = 29; i >= 0; i--) {
        if (cur == -1) continue;
        if ((n & 1 << i) > 0) {
            if (tree[cur].adj[0] != -1) {
                cur = tree[cur].adj[0];
                res ^= 1 << i;
            } else {
                cur = tree[cur].adj[1];
            }
        } else {
            if (tree[cur].adj[1] != -1) {
                cur = tree[cur].adj[1];
                res ^= 1 << i;
            } else {
                cur = tree[cur].adj[0];
            }
        }
    }
    return res;
}

void dfs(vector<vector<int>> &adj, vector<int> &tour, vector<int> &size, int u) {
    tour.pb(u);
    size[u] = 1;
    for (int v : adj[u]) {
        dfs(adj, tour, size, v);
        size[u] += size[v];
    }
}

void solve() {
    int Q; cin >> Q;
    vector<vector<int>> adj(1);
    vector<int> sum = {0};
    vector<vector<int>> queries;
    for (int q = 0; q < Q; q++) {
        string type; cin >> type;
        if (type == "Add") {
            int p, k; cin >> p >> k; p--;
            adj[p].pb(sz(adj));
            queries.pb({0, sz(adj)});
            adj.pb({});
            sum.pb(sum[p] ^ k);
        } else {
            int u, v; cin >> u >> v; u--; v--;
            queries.pb({1, u, v});
        }
    }
    int N = sz(adj);
    vector<int> tour, size(N);
    dfs(adj, tour, size, 0);
    vector<int> start(N);
    for (int i = 0; i < N; i++) {
        start[tour[i]] = i;
    }
    int M = 1; while (M < N) M <<= 1;
    vector<vector<node>> tree(M * 2);
    for (int i = 0; i < M * 2; i++) {
        tree[i] = vector<node>(1);
    }
    int n = M;
    while (n > 0) {
        add(tree[n], sum[0]);
        n >>= 1;
    }
    for (vector<int> query : queries) {
        if (query[0] == 0) {
            int u = query[1];
            n = start[u] + M;
            while (n > 0) {
                add(tree[n], sum[u]);
                n >>= 1;
            }
        } else {
            int u = query[1], v = query[2];
            int l = start[v] + M, r = l + size[v] - 1;
            int res = 0;
            while (l <= r) {
                if (l % 2 == 1) {
                    res = max(res, maxXor(tree[l], sum[u]));
                    l >>= 1;
                    l++;
                } else {
                    l >>= 1;
                }
                if (r % 2 == 0) {
                    res = max(res, maxXor(tree[r], sum[u]));
                    r >>= 1;
                    r--;
                } else {
                    r >>= 1;
                }
            }
            cout << res << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
    
    solve();
 
    return 0;
}

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