Submission #470704

#	Time	Username	Problem	Language	Result	Execution time	Memory
470704		naman1601	Klasika (COCI20_klasika)	C++17	110 / 110	3213 ms	511068 KiB

klasika

/*
++[---------->+<]>.-[------>+<]>-.++++++++.+++++.-[->+++++<]>-.-[--->++<]>--.+.[--->+<]>---.[->+++<]>++.++++++.-------.++++++.--[--->+<]>.-[->+++<]>-..+++++++++++++.[----->++<]>.------------.+[----->+<]>.--------.+++++++++++++.-------------.--[--->+<]>-.---[->++++<]>-.++++[->+++<]>.--[--->+<]>-.[->+++<]>++.-.+++.---.-[->+++<]>.-[--->++<]>+.++++.------.[--->+<]>---.+[----->+<]>.------------.+++++++.-------.--[--->+<]>---.+++[->+++<]>++..+++++++++.---------.-[->+++<]>.+[----->+<]>+.-------------.+++++++.+.----[->+++<]>-.
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long big;
typedef long double ludo;
#define pbb pair<big, big>
#define pii pair<int, int>
#define fe first
#define se second
#define maxheap priority_queue
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define fr(i, s, e) for(int i = s; i < e; i++)
#define revfr(i, s, e) for(int i = s - 1; i >= e; i--)
#define getv(v, n) for(int i = 0; i < n; i++) cin >> v[i];
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL)
#define nl "\n"
// #define debug(text) if(do_debug) {cout << (#text) << ": " << text << endl;}
#ifdef naman1601
#define debug(text) cout << (#text) << ": " << text << endl;
#else
#define debug(text)
#endif

const big mod = 1000000007;
// const big mod = 998244353;
const big infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;


const int maxn = 2e5 + 5;
int n_nodes;
int size_of_tree;
vector<pbb> adj[maxn];
vector<array<big, 3>> queries;
int mapper[maxn] = {0}, in[maxn] = {0}, out[maxn] = {0};
big from_root[maxn] = {0};


struct node {

	int leaf = 0;
	int next[2] = {0};
	set<int> set_in;
};

vector<node> trie(1);

void add(big val, int node) {

	int v = 0;

	revfr(bit, 31, 0) {

		int is_set = 0;

		if(val & (1 << bit)) {

			is_set++;
		}

		if(!trie[v].next[is_set]) {

			trie[v].next[is_set] = trie.size();
			trie.emplace_back();
		}

		v = trie[v].next[is_set];
		trie[v].set_in.insert(in[node]);
	}

	trie[v].leaf = 1;
}

big query(big val, int node) {

	int v = 0;
	big rv = 0;

	revfr(bit, 31, 0) {

		int is_set = 0;

		if(val & (1 << bit)) {

			is_set++;
		}

		int preferred = !is_set;
		int not_preferred = !preferred;

		if(trie[v].next[preferred]) {

			auto it = trie[trie[v].next[preferred]].set_in.lower_bound(in[node]);

			if(it != trie[trie[v].next[preferred]].set_in.end() && *it <= out[node]) {

				rv ^= preferred * (1 << bit);
				v = trie[v].next[preferred];

			} else {

				rv ^= not_preferred * (1 << bit);
				v = trie[v].next[not_preferred];
			}

		} else {

			rv ^= not_preferred * (1 << bit);
			v = trie[v].next[not_preferred];
		}
	}

	return rv;
}


void dfs(int v, int p) {

	in[v] = size_of_tree++;

	for(auto edge : adj[v]) {

		int u = edge.fe;

		if(u == p) {

			continue;
		}

		dfs(u, v);
	}

	out[v] = size_of_tree - 1;
}


void solve() {

	int nq;
	cin >> nq;	

	queries.reserve(nq);

	size_of_tree = 1;

	fr(i, 0, nq) {

		string type;
		int ty = 2;
		big u, v;
		cin >> type >> u >> v;

		if(type == "Add") {

			ty = 1;
			size_of_tree++;
			adj[u].push_back(make_pair(size_of_tree, v));
		}

		queries.push_back({ty, u, v});
	}

	size_of_tree = 0;
	dfs(1, 1);

	size_of_tree = 1;

	// for(auto q : queries) {

	// 	if(q[0] == 2) {

	// 		continue;
	// 	}

	// 	size_of_tree++;
	// 	from_root[size_of_tree] = from_root[q[1]] ^ q[2];
	// 	add(from_root[size_of_tree], size_of_tree);
	// }

	add(0, 1);

	for(auto q : queries) {

		if(q[0] == 1) {

			size_of_tree++;
			from_root[size_of_tree] = from_root[q[1]] ^ q[2];
			add(from_root[size_of_tree], size_of_tree);
			continue;
		}

		int u = q[1], v = q[2];
		big ans = from_root[u];
		ans ^= query(ans, v);
		cout << ans << nl;
	}
}


int main() {
	
	speed;

	int q = 1;
	// cin >> q;

	while(q-- > 0) {

		solve();
	}

	return 0;
}

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