Submission #891765

#	Time	Username	Problem	Language	Result	Execution time	Memory
891765		Fucsdeptrai	Klasika (COCI20_klasika)	C++17	110 / 110	2084 ms	431976 KiB

klasika

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e5 + 9;
const int Log = 30;

struct Node
{
    Node *c[2];
    set<int> idx;

    Node()
    {
        c[0] = c[1] = NULL;
    }
} *Trie;

int n, m, q, Timer;
int d[N], num[N], tail[N];
vector<pair<int, int>> adj[N];
vector<pair<int, pair<int, int>>> que;

void Dfs(int u = 1, int du = 0)
{
    num[u] = ++Timer;
    d[u] = du;
    for(auto [v, w] : adj[u])
    {
        Dfs(v, du^w);
    }
    tail[u] = Timer;
}

int Get(Node *p, int x, int y)
{
    for(int i = Log;i >= 0;i --)
    {
        bool w = (1<<i)&x;
        if(p->c[w^1] != NULL and (p->c[w^1]->idx.lower_bound(num[y]) != p->c[w^1]->idx.upper_bound(tail[y])))
        {
            x ^= ((w^1) << i);
            p=p->c[w^1];
        }
        else
        {
            x ^= (w<<i);
            p=p->c[w];
        }
    }
    return x;
}

void Add(Node *p, int x, int y)
{
    for(int i = Log;i >= 0;i --)
    {
        bool w = (1<<i)&x;
        if(p->c[w]==NULL) p->c[w] = new Node();
        p=p->c[w];
        p->idx.insert(y);
    }
}

void Solve()
{
    cin>>q;
    ++n;
    while(q--)
    {
        string Type; cin>>Type;
        int x, y; cin >> x >> y;
        if(Type == "Add")
        {
            adj[x].push_back({++n, y});
            que.push_back({0, {n, n}});
        }
        else
        {
            que.push_back({1, {x, y}});
        }
    }

    Dfs();
    Trie = new Node();
    Add(Trie, 0, 1);
    for(auto [Type, xy] : que)
    {
        auto [x, y] = xy;
        if(Type)
        {
            cout << Get(Trie, d[x], y) << '\n';
        }
        else
        {
            Add(Trie, d[x], num[x]);
        }
    }
}

signed main()
{
//	ios_base::sync_with_stdio(0);
//	cin.tie(0);

	int TC = 1;
//	cin>>TC;
    while(TC--)
    {
        Solve();
    }
}

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