Submission #446491

#	Time	Username	Problem	Language	Result	Execution time	Memory
446491		Saboon	Klasika (COCI20_klasika)	C++17	110 / 110	3131 ms	435916 KiB

klasika

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 5;

int typ[maxn], q1[maxn], q2[maxn];
int par[maxn];
vector<int> t[maxn];
int Time = 1, st[maxn], ft[maxn];

struct Trie{
	struct node{
		node* lc;
		node* rc;
		set<int> s;
		bool find(int l, int r){
			auto it = s.lower_bound(l);
			if (it == s.end() or r <= *it)
				return 0;
			return 1;
		}
	};
	node* root;
	Trie(){
		root = new node;
	}
	void add(int x, int idx){
		node* now = root;
		now->s.insert(idx);
		for (int i = 30; i >= 0; i--){
			if (x & (1 << i)){
				if (now->rc == NULL)
					now->rc = new node;
				now = now->rc;
			}
			else{
				if (now->lc == NULL)
					now->lc = new node;
				now = now->lc;
			}
			now->s.insert(idx);
		}
	}
	int get(int x, int l, int r){
		node* now = root;
		int ret = 0;
		for (int i = 30; i >= 0; i--){
			if (x & (1 << i)){
				if (now->lc != NULL and now->lc->find(l, r)){
					ret |= (1 << i);
					now = now->lc;
				}
				else
					now = now->rc;
			}
			else{
				if (now->rc != NULL and now->rc->find(l, r)){
					ret |= (1 << i);
					now = now->rc;
				}
				else
					now = now->lc;
			}
		}
		return ret;
	}
};

void dfs(int v){
	st[v] = Time ++;
	for (auto u : t[v])
		dfs(u);
	ft[v] = Time;
}

int main(){
	ios_base::sync_with_stdio(false);
	int q;
	cin >> q;
	int n = 1;
	for (int i = 1; i <= q; i++){
		string type;
		int x, y;
		cin >> type >> x >> y;
		typ[i] = 1, q1[i] = x, q2[i] = y;
		if (type == "Add"){
			t[x].push_back(++n);
			typ[i] = 0;
			par[n] = (par[x] ^ y);
		}
	}
	dfs(1);
	Trie T;
	T.add(par[1], st[1]);
	int m = 2;
	for (int i = 1; i <= q; i++){
		if (typ[i] == 0){
			int x = q1[i], y = q2[i];
			T.add(par[m], st[m]);
			m ++;
		}
		else{
			int x = q1[i], y = q2[i];
			cout << T.get(par[x], st[y], ft[y]) << '\n';
		}
	}
}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:100:8: warning: unused variable 'x' [-Wunused-variable]
  100 |    int x = q1[i], y = q2[i];
      |        ^
klasika.cpp:100:19: warning: unused variable 'y' [-Wunused-variable]
  100 |    int x = q1[i], y = q2[i];
      |                   ^

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