Submission #689554

#	Time	Username	Problem	Language	Result	Execution time	Memory
689554		danikoynov	Klasika (COCI20_klasika)	C++14	110 / 110	2345 ms	457804 KiB

klasika

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

struct trie
{
    int depth;
    set < int > in_times;
    trie *child[2];

    trie(int _depth)
    {
        depth = _depth;
        child[0] = child[1] = NULL;
    }
};

const int maxn = 400100;

struct query
{
    int x, y;
    string type;
}ask[maxn];

int n = 1, q;
vector < pair < int, int > > g[maxn];

int xor_depth[maxn], f[maxn], timer, tin[maxn], tout[maxn];
void dfs(int v)
{
    f[++ timer] = v;
    tin[v] = timer;

    for (pair < int, int > nb : g[v])
    {
        int u = nb.first;
        xor_depth[u] = (xor_depth[v] ^ nb.second);
        dfs(u);
    }

    tout[v] = timer;
}

void add(trie *root, int val, int pos)
{
    root -> in_times.insert(pos);
    if (root -> depth < 0)
        return;

    int bit = (1 << root -> depth), type = ((bit & val) > 0);
    if (root -> child[type] == NULL)
        root -> child[type] = new trie(root -> depth - 1);

    add(root -> child[type], val, pos);
}

bool in_interval(trie *cur, int left, int right)
{
    set < int > :: iterator it = cur -> in_times.lower_bound(left);
    if (it == cur -> in_times.end() ||
        *it > right)
            return false;
    return true;
}

int query(trie *root, int x, int left, int right)
{
    if (root -> depth < 0)
        return 0;

    int bit = (1 << root -> depth), type = (((bit & x) > 0) + 1) % 2;
    if (root -> child[type] == NULL ||
        !in_interval(root -> child[type], left, right))
            return query(root -> child[(type + 1) % 2], x, left, right);
    return query(root -> child[type], x, left, right) + bit;
}

trie *root = new trie(30);

void add_node(int ver)
{
    add(root, xor_depth[ver], tin[ver]);
}

void solve()
{
    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        cin >> ask[i].type >> ask[i].x >> ask[i].y;
        if (ask[i].type == "Add")
            g[ask[i].x].push_back({++ n, ask[i].y});

    }

    dfs(1);
    add_node(1);

    int ver_cnt = 1;
    for (int i = 1; i <= q; i ++)
    {
        if (ask[i].type == "Add")
        {
            add_node(++ ver_cnt);
        }
        else
        {

            int a = ask[i].x, b = ask[i].y;
            int ans = query(root, xor_depth[a], tin[b], tout[b]);
            cout << ans << endl;
        }
    }
}

int main()
{
    speed();
    solve();
    return 0;
}
/**

*/

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