Submission #1310634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310634		iamhereforfun	Klasika (COCI20_klasika)	C++20	0 / 110	201 ms	114048 KiB

klasika

// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 2e5 + 5;
const int M = 1e6 + 5;
const int LG = 31;
const int C = 26;
const long long INF = 1e18 + 5;
const int B = 400;
const int MOD = 998244353;

struct Node
{
    Node *child[2];
    set<int> st;
    Node()
    {
        child[0] = child[1] = NULL;
    }
};

struct Trie
{
    Node *root;
    string ans;
    Trie()
    {
        root = new Node();
    }
    void update(int i, int j)
    {
        Node *p = root;
        for (int x = LG - 1; x >= 0; x--)
        {
            int k = i >> x & 1;
            if (!p->child[k])
            {
                p->child[k] = new Node();
            }
            p = p->child[k];
            p->st.insert(j);
        }
    }
    int get(int i, int st, int en)
    {
        Node *p = root;
        int ans = 0;
        for (int x = LG - 1; x >= 0; x--)
        {
            int k = i >> x & 1;
            k = !k;
            if (p->child[k])
            {
                auto it = p->child[k]->st.lower_bound(st);
                if (it != p->child[k]->st.end() && *it <= en)
                {
                    p = p->child[k];
                    ans += (1 << x);
                    continue;
                }
            }
            if (p->child[!k])
            {
                p = p->child[!k];
            }
            return 0;
        }
        return ans;
    }
};

int q, cid, st[N], en[N], val[N];
vector<array<int, 3>> query;
vector<int> adj[N];

void dfs(int c)
{
    st[c] = cid++;
    for (int i : adj[c])
    {
        dfs(i);
    }
    en[c] = cid - 1;
}

void solve()
{
    cin >> q;
    cid = 1;
    for (int x = 0; x < q; x++)
    {
        string s;
        cin >> s;
        int t, a, b;
        cin >> a >> b;
        t = s == "Add";
        query.push_back({t, a, b});
        if (t == 1)
        {
            cid++;
            adj[a].push_back(cid);
            val[cid] = val[a] ^ b;
        }
    }
    cid = 0;
    dfs(1);
    Trie trie;
    cid = 1;
    for (int x = 0; x < q; x++)
    {
        auto &[t, a, b] = query[x];
        if (t == 1)
        {
            cid++;
            trie.update(val[cid], st[cid]);
        }
        else
        {
            cout << trie.get(val[a], st[b], en[b]) << "\n";
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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