Submission #487900

#	Time	Username	Problem	Language	Result	Execution time	Memory
487900		hoanghq2004	Klasika (COCI20_klasika)	C++14	33 / 110	1148 ms	524292 KiB

klasika

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

const int Nmax = 2e5 + 10;

struct Trie {
    vector <array <int, 2> > to;
    int sz = 0;
    Trie() {
        to.push_back(array <int, 2>({0, 0}));
    }
    void add(int x) {
        int u = 0;
        for (int i = 29; i >= 0; --i) {
            if (to[u][x >> i & 1] == 0) {
                to.push_back(array <int, 2>({0, 0}));
                to[u][x >> i & 1] = ++sz;
            }
            u = to[u][x >> i & 1];
        }
    }
    int get(int x) {
        if (sz == 0) return -1;
        int u = 0;
        int ans = 0;
        for (int i = 29; i >= 0; --i) {
            if (to[u][x >> i & 1 ^ 1]) {
                ans += (1 << i);
                u = to[u][x >> i & 1 ^ 1];
            } else u = to[u][x >> i & 1];
        }
        return ans;
    }
};

int q;
vector <pair <int, int> > e[Nmax];
int in[Nmax], out[Nmax], ti, d[Nmax];

void dfs(int u) {
    in[u] = ++ti;
    for (auto [v, w]: e[u]) {
        d[v] = d[u] ^ w;
        dfs(v);
    }
    out[u] = ti;
}

Trie st[Nmax * 4];

void add(int id, int L, int R, int i, int val) {
    st[id].add(val);
    if (L == R) return;
    int mid = L + R >> 1;
    if (i <= mid) add(id * 2, L, mid, i, val);
    else add(id * 2 + 1, mid + 1, R, i, val);
}

int get(int id, int L, int R, int u, int v, int val) {
    if (u > R || L > v) return -1;
    if (u <= L && R <= v) return st[id].get(val);
    int mid = L + R >> 1;
    return max(get(id * 2, L, mid, u, v, val), get(id * 2 + 1, mid + 1, R, u, v, val));
}

vector <tuple <string, int, int> > queries;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> q;
    int n = 1;
    while (q--) {
        string s;
        int x, y;
        cin >> s >> x >> y;
        if (s == "Add") ++n, e[x].push_back({n, y}), queries.push_back({s, n, y});
        else queries.push_back({s, x, y});
    }
    dfs(1);
    add(1, 1, n, in[1], 0);
    for (auto [s, x, y]: queries) {
        if (s == "Add") add(1, 1, n, in[x], d[x]);
        else cout << get(1, 1, n, in[y], out[y], d[x]) << '\n';
    }
}

Compilation message (stderr)

klasika.cpp: In member function 'int Trie::get(int)':
klasika.cpp:30:30: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   30 |             if (to[u][x >> i & 1 ^ 1]) {
      |                       ~~~~~~~^~~
klasika.cpp:32:34: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   32 |                 u = to[u][x >> i & 1 ^ 1];
      |                           ~~~~~~~^~~
klasika.cpp: In function 'void dfs(int)':
klasika.cpp:45:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for (auto [v, w]: e[u]) {
      |               ^
klasika.cpp: In function 'void add(int, int, int, int, int)':
klasika.cpp:57:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid = L + R >> 1;
      |               ~~^~~
klasika.cpp: In function 'int get(int, int, int, int, int, int)':
klasika.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     int mid = L + R >> 1;
      |               ~~^~~
klasika.cpp: In function 'int main()':
klasika.cpp:84:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     for (auto [s, x, y]: queries) {
      |               ^

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