Submission #405234

#	Time	Username	Problem	Language	Result	Execution time	Memory
405234		ngpin04	Klasika (COCI20_klasika)	C++14	110 / 110	2631 ms	426532 KiB

klasika

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 2e5 + 5; 

struct node {
	set <int> s;
	node* ptr[2];

	node() {
		s.clear();
		ptr[0] = ptr[1] = nullptr;
	}
};

node *root = new node();

vector <int> adj[N];
 
pair <int, int> pir[N];

int tin[N];
int val[N];
int tout[N];
int n = 1,q,timer;
 
string op[N];

int getbit(int x, int i) {
	return (x >> i) & 1;
}

void dfs(int u) {
	tin[u] = ++timer;
	for (int v : adj[u])
		dfs(v);
	tout[u] = timer;
}

void add(int x, int id) {
	node* cur = root;

	for (int i = 29; i >= 0; i--) {
		node* &p = cur->ptr[getbit(x, i)];
		if (p == nullptr) 
			p = new node();
		cur = p;
		cur->s.insert(id);
	}
}

int getmax(int x, int l, int r) {
	node *cur = root;
	int res = 0;
	for (int i = 29; i >= 0; i--) {
		bool found = false;
		for (int val = 1; val >= 0; val--) {
			node *p = cur->ptr[val ^ getbit(x, i)];

			if (p == nullptr)
				continue;
			auto it = p->s.lower_bound(l);
			if (it == p->s.end() || *it > r)
				continue;

			found = true;
			res |= (val << i);
			cur = p;
			break;
		}
		if (!found)
			return -1;
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> q;
	for (int i = 1; i <= q; i++) 
		cin >> op[i] >> pir[i].fi >> pir[i].se;
	
	for (int i = 1; i <= q; i++) if (op[i] == "Add") {
		val[++n] = val[pir[i].fi] ^ pir[i].se;
		adj[pir[i].fi].push_back(n);
		pir[i].fi = n;
	}	
 
	dfs(1);

	add(val[1], tin[1]);
	for (int i = 1; i <= q; i++) {
		if (op[i] == "Add")
			add(val[pir[i].fi], tin[pir[i].fi]);
		else {
			int l = tin[pir[i].se];
			int r = tout[pir[i].se];
			cout << getmax(val[pir[i].fi], l, r) << "\n";
		} 

	}
	return 0;
}	

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