Submission #1289019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289019		nemkho	Klasika (COCI20_klasika)	C++17	33 / 110	2023 ms	562044 KiB

klasika

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int n, cnt, sta[N], q, en[N];
ll XOR[N];
vector <int> a[N];
struct haha
{
    int from, to, type;
};
vector<haha> query;
struct Trie
{
    set <int> tour[6000001];
    int child[6000001][2], m = 0;
    void add (ll x, int st)
    {
        int u = 0;
        for (int i = 30; i >= 0; i--)
        {
            bool k = (x & (1 << i));
            if (child[u][k] == 0)
                child[u][k] = ++m;
            tour[u].insert(st);
            u = child[u][k];
        }
        tour[u].insert(st);
    }
    ll get (ll x, int l, int r)
    {
        int u = 0;
        ll res = 0;
        for (int i = 30; i >= 0; i--)
        {
            bool k = (x & (1 << i));
            if (child[u][k^1] != 0)
            {
                set <int>::iterator it = tour[child[u][k^1]].lower_bound(l);
                if (it == tour[child[u][k^1]].end() || *it > r)
                    u = child[u][k];
                else
                {
                    u = child[u][k^1];
                    res += (1LL << i);
                }
            }
            else
                u = child[u][k];
        }
        return res;
    }
} trie;

void inp()
{
    n = 1;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        string task;
        cin >> task;
        if (task == "Add")
        {
            int x, y;
            cin >> x >> y;
            n++;
            XOR[n] = XOR[x] ^ y;
            a[x].push_back(n);
            a[n].push_back(x);
            query.push_back({n, -1, 1});
        }
        else
        {
            int x, y;
            cin >> x >> y;
            query.push_back({x, y, 0});
        }
    }
}
void dfs (int u, int pre)
{
    sta[u] = ++cnt;
    for (int v : a[u])
    {
        if (v == pre)
            continue;
        dfs(v, u);
    }
    en[u] = cnt;
}
void solve()
{
    dfs(1, 0);
    trie.add(0, 1);
    for (haha i : query)
    {
        int u = i.from, v = i.to, task = i.type;
        if (task == 0)
            cout << trie.get(XOR[u], sta[v], en[v]) << "\n";
        else
            trie.add(XOR[u], sta[u]);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    inp();
    solve();
}

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