Submission #1087785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087785		MinhKien	Klasika (COCI20_klasika)	C++17	0 / 110	226 ms	77892 KiB

klasika

#include <iostream>
#include <string>
#include <vector>
#include <set>

#define int long long
using namespace std;

const int N = 2e5 + 10;
const int LG = 30;

int q, x[N];
int child[N];

vector <int> v[N];
int num[N], last[N], cnt, k = 1;
void dfs(int s) {
    num[s] = last[s] = ++cnt;

    for (int z: v[s]) {
        dfs(z);
    }
    last[s] = cnt;
}

struct Trie {
    struct node {
        node *child[2];
        set <int> s;

        node () {
            child[0] = child[1] = nullptr;
            s.clear();
        }
    };

    node *root;
    Trie () {
        root = new node ();
    }

    void add_num(int val, int Num) {
        node *cur = root;
        for (int i = LG; i >= 0; --i) {
            int c = val >> i & 1;
            if (cur->child[c] == nullptr) cur->child[c] = new node();
            cur = cur->child[c];
            cur->s.insert(Num);
        }
    }

    bool in(node *x, int l, int r) {
        set <int> :: iterator it = x->s.lower_bound(l);
        if (it == x->s.end() || *it > r) return false;
    }

    int solve(int val, int b) {
        int ans = 0;
        node *cur = root;

        for (int i = LG; i >= 0; --i) {
            int c = (val >> i & 1) ^ 1;

            if (cur->child[c] != nullptr && in(cur->child[c], num[b], last[b])) {
                cur = cur->child[c];
                ans |= (1 << i);
            } else {
                if (cur->child[c ^ 1] != nullptr && in(cur->child[c ^ 1], num[b], last[b])) {
                    cur = cur->child[c ^ 1];
                } else {
                    return ans;
                }
            }
        }

        return ans;
    }
} T;

struct query {
    string t;
    int a, b;
} Q[N];

signed main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    cin >> q;
    k = 1;
    for (int i = 1; i <= q; ++i) {
        cin >> Q[i].t >> Q[i].a >> Q[i].b;

        if (Q[i].t == "Add") {
            v[Q[i].a].push_back(++k);
            child[i] = k;
        }
    }

    dfs(1);

    for (int i = 1; i <= q; ++i) {
        if (Q[i].t == "Add") {
            k = child[i];
            T.add_num(x[k], num[k]);
        } else {
            cout << T.solve(x[Q[i].a], Q[i].b) << "\n";
        }
    }

    return 0;
}

Compilation message (stderr)

klasika.cpp: In member function 'bool Trie::in(Trie::node*, long long int, long long int)':
klasika.cpp:55:5: warning: control reaches end of non-void function [-Wreturn-type]
   55 |     }
      |     ^

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