Submission #470704

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
470704	2021-09-05T07:30:44 Z	naman1601	Klasika (COCI20_klasika)	C++17	110 / 110	3213 ms	511068 KB

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.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5196 KB	Output is correct
2	Correct	4 ms	5196 KB	Output is correct
3	Correct	5 ms	5444 KB	Output is correct
4	Correct	4 ms	5528 KB	Output is correct
5	Correct	4 ms	5068 KB	Output is correct
6	Correct	4 ms	5196 KB	Output is correct
7	Correct	4 ms	5444 KB	Output is correct
8	Correct	4 ms	5444 KB	Output is correct
9	Correct	4 ms	5224 KB	Output is correct
10	Correct	4 ms	5408 KB	Output is correct
11	Correct	4 ms	5444 KB	Output is correct
12	Correct	4 ms	5444 KB	Output is correct

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5196 KB	Output is correct
2	Correct	4 ms	5196 KB	Output is correct
3	Correct	5 ms	5444 KB	Output is correct
4	Correct	4 ms	5528 KB	Output is correct
5	Correct	4 ms	5068 KB	Output is correct
6	Correct	4 ms	5196 KB	Output is correct
7	Correct	4 ms	5444 KB	Output is correct
8	Correct	4 ms	5444 KB	Output is correct
9	Correct	4 ms	5224 KB	Output is correct
10	Correct	4 ms	5408 KB	Output is correct
11	Correct	4 ms	5444 KB	Output is correct
12	Correct	4 ms	5444 KB	Output is correct
13	Correct	8 ms	6724 KB	Output is correct
14	Correct	10 ms	8384 KB	Output is correct
15	Correct	13 ms	8544 KB	Output is correct
16	Correct	14 ms	11708 KB	Output is correct
17	Correct	8 ms	6596 KB	Output is correct
18	Correct	10 ms	8256 KB	Output is correct
19	Correct	14 ms	8508 KB	Output is correct
20	Correct	14 ms	9532 KB	Output is correct
21	Correct	7 ms	6596 KB	Output is correct
22	Correct	10 ms	8224 KB	Output is correct
23	Correct	14 ms	8440 KB	Output is correct
24	Correct	14 ms	9520 KB	Output is correct

Subtask #3

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	897 ms	127800 KB	Output is correct
2	Correct	1544 ms	254420 KB	Output is correct
3	Correct	2031 ms	305796 KB	Output is correct
4	Correct	2748 ms	510872 KB	Output is correct
5	Correct	963 ms	128536 KB	Output is correct
6	Correct	1665 ms	250216 KB	Output is correct
7	Correct	2179 ms	300236 KB	Output is correct
8	Correct	2952 ms	502420 KB	Output is correct
9	Correct	868 ms	128976 KB	Output is correct
10	Correct	1622 ms	250944 KB	Output is correct
11	Correct	2140 ms	302424 KB	Output is correct
12	Correct	2806 ms	503892 KB	Output is correct

Subtask #4

44.0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5196 KB	Output is correct
2	Correct	4 ms	5196 KB	Output is correct
3	Correct	5 ms	5444 KB	Output is correct
4	Correct	4 ms	5528 KB	Output is correct
5	Correct	4 ms	5068 KB	Output is correct
6	Correct	4 ms	5196 KB	Output is correct
7	Correct	4 ms	5444 KB	Output is correct
8	Correct	4 ms	5444 KB	Output is correct
9	Correct	4 ms	5224 KB	Output is correct
10	Correct	4 ms	5408 KB	Output is correct
11	Correct	4 ms	5444 KB	Output is correct
12	Correct	4 ms	5444 KB	Output is correct
13	Correct	8 ms	6724 KB	Output is correct
14	Correct	10 ms	8384 KB	Output is correct
15	Correct	13 ms	8544 KB	Output is correct
16	Correct	14 ms	11708 KB	Output is correct
17	Correct	8 ms	6596 KB	Output is correct
18	Correct	10 ms	8256 KB	Output is correct
19	Correct	14 ms	8508 KB	Output is correct
20	Correct	14 ms	9532 KB	Output is correct
21	Correct	7 ms	6596 KB	Output is correct
22	Correct	10 ms	8224 KB	Output is correct
23	Correct	14 ms	8440 KB	Output is correct
24	Correct	14 ms	9520 KB	Output is correct
25	Correct	897 ms	127800 KB	Output is correct
26	Correct	1544 ms	254420 KB	Output is correct
27	Correct	2031 ms	305796 KB	Output is correct
28	Correct	2748 ms	510872 KB	Output is correct
29	Correct	963 ms	128536 KB	Output is correct
30	Correct	1665 ms	250216 KB	Output is correct
31	Correct	2179 ms	300236 KB	Output is correct
32	Correct	2952 ms	502420 KB	Output is correct
33	Correct	868 ms	128976 KB	Output is correct
34	Correct	1622 ms	250944 KB	Output is correct
35	Correct	2140 ms	302424 KB	Output is correct
36	Correct	2806 ms	503892 KB	Output is correct
37	Correct	1305 ms	131216 KB	Output is correct
38	Correct	1922 ms	254840 KB	Output is correct
39	Correct	2413 ms	308128 KB	Output is correct
40	Correct	2918 ms	511068 KB	Output is correct
41	Correct	1484 ms	129088 KB	Output is correct
42	Correct	2140 ms	250480 KB	Output is correct
43	Correct	2613 ms	300324 KB	Output is correct
44	Correct	3213 ms	502672 KB	Output is correct
45	Correct	1534 ms	129440 KB	Output is correct
46	Correct	2262 ms	251300 KB	Output is correct
47	Correct	2699 ms	301152 KB	Output is correct
48	Correct	3049 ms	504120 KB	Output is correct