Submission #1093096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093096		Hacv16	Klasika (COCI20_klasika)	C++17	110 / 110	2137 ms	475440 KiB

klasika

#include <bits/stdc++.h>
using namespace std;

const int MAX = 2e5 + 15;
const int LOG = 31;

int n = 1, q, x[MAX];
int timer, tin[MAX], tout[MAX];

vector<int> adj[MAX];

struct Trie
{
    int numNodes;
    vector<array<int, 2>> trie;
    vector<set<int>> myTins;

    int create()
    {
    	trie.push_back({ 0, 0 });
        set<int> aux; myTins.push_back(aux);
    	return numNodes++;
    }

    Trie(void){ numNodes = 0; create(); }

    bool check(int node, int curTin, int curTout)
    {
        auto it = myTins[node].lower_bound(curTin);
        if(it == myTins[node].end()) return false;
        return (bool)(*it <= curTout);
    }

    void add(int x, int curTin)
    {
    	int cur = 0;

    	for(int i = LOG - 1; i >= 0; i--)
    	{
    		bool id = (x & (1 << i));

    		if(trie[cur][id] == 0)
    		{
    			int newNode = create();
    			trie[cur][id] = newNode;
    		}

            cur = trie[cur][id];
            myTins[cur].insert(curTin);
		}
    }

    int query(int x, int curTin, int curTout)
	{
    	int cur = 0, resp = 0;

    	for(int i = LOG - 1; i >= 0; i--)
    	{
    		bool id = (x & (1 << i));

    		if(trie[cur][!id] != 0 && check(trie[cur][!id], curTin, curTout)){
    			resp ^= (1 << i);
    			cur = trie[cur][!id];

    		} else if(trie[cur][id] != 0 && check(trie[cur][id], curTin, curTout)){
                cur = trie[cur][id];

            } else return 0;
    	}

    	return resp;
    }

};

void dfs(int u, int p)
{
    tin[u] = ++timer;

    for(auto v : adj[u])
    {
    	if(v == p) continue;
    	dfs(v, u);
	}

	tout[u] = timer;
}
int32_t main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> q;

    vector<tuple<int, int, int>> events;

    events.emplace_back(1, 1, x[1]);

    while(q--)
    {
    	string op; cin >> op;

    	if(op == "Add")
    	{
    		int p, w; cin >> p >> w;
    		int newNode = ++n;

    		x[newNode] = x[p] ^ w;

    		adj[p].push_back(newNode);
    		adj[newNode].push_back(p);

    		events.emplace_back(1, newNode, x[newNode]);

    	}else{
    		int a, b; cin >> a >> b;
    		events.emplace_back(2, x[a], b);
    	}
    }

    dfs(1, 1);
    Trie T = Trie();

    for(auto [type, x, y] : events)
    {
    	if(type == 1) T.add(y, tin[x]);
    	else cout << T.query(x, tin[y], tout[y]) << '\n';
    }

    cout << '\n';
}

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