Submission #855909

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
855909	2023-10-02T08:54:18 Z	wakandaaa	Klasika (COCI20_klasika)	C++17	110 / 110	2069 ms	435380 KB

klasika

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 520
#endif

const int N = 2e5 + 5;
const int MOD = 1e9 + 7; // 998244353
const int inf = INT_MAX; // LLONG_MAX
const int LOG = 30;
template<class T> bool minimize(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool maximize(T &a, T b) { return a < b ? (a = b, true) : false; }
template<class T> bool add(T &a, T b) { a += b; while (a > MOD) a -= MOD; return true; }

#define BIT(x, i) (((x) >> (i)) & 1)

struct TrieNode {
	set<int> s;
	TrieNode *child[2];
	TrieNode() {
		child[0] = child[1] = NULL;
	}
};

struct Trie {
	TrieNode *root;
	Trie() {
		root = new TrieNode();
	}
	void add(int value, int id) {
		TrieNode *p = root;
		for (int i = LOG; i >= 0; --i) {
			int c = BIT(value, i);
			if (p->child[c] == NULL) p->child[c] = new TrieNode();
			p = p->child[c];
			p->s.insert(id);
		}
	}
	int get(int value, int L, int R) {
		int ans = 0;
		TrieNode *p = root;
		for (int i = LOG; i >= 0; --i) {
			int c = BIT(value, i);
			c ^= 1;
			if (p->child[c] == NULL || p->child[c]->s.lower_bound(L) == p->child[c]->s.upper_bound(R)) p = p->child[c ^ 1];
			else {
				ans += (1 << i);
				p = p->child[c];
			}
		}
		return ans;
	}
} trie;

struct Query {
	int type, x, y;
};

vector<pair<int, int> > g[N];
int St[N], Ft[N], Rxor[N];
vector<Query> Q;
int Time = 0;

void DFS(int u, int p, int L) {
	St[u] = ++Time;
	Rxor[u] = L;
	for (auto [v, w] : g[u]) if (v != p) {
		DFS(v, u, w ^ L);
	}
	Ft[u] = Time;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n = 1;
	int q; cin >> q;
	while (q--) {
		string s; cin >> s;
		int x, y; cin >> x >> y;
		--x;
		if (s == "Add") {
			Q.push_back({0, n, y});
			g[x].push_back({n, y});
			g[n].push_back({x, y});
			++n;
		} else {
			--y;
			Q.push_back({1, x, y});
		}
	}

	DFS(0, -1, 0);
	trie.add(0, St[0]);

	for (auto [type, x, y] : Q) {
		if (type == 0) trie.add(Rxor[x], St[x]);
		else cout << trie.get(Rxor[x], St[y], Ft[y]) << '\n';
	}

	return 0;
}
// I'm thinking out loud!

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7512 KB	Output is correct
2	Correct	2 ms	7516 KB	Output is correct
3	Correct	2 ms	7516 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7328 KB	Output is correct
6	Correct	3 ms	7772 KB	Output is correct
7	Correct	2 ms	7516 KB	Output is correct
8	Correct	2 ms	7860 KB	Output is correct
9	Correct	2 ms	7260 KB	Output is correct
10	Correct	2 ms	7588 KB	Output is correct
11	Correct	2 ms	7768 KB	Output is correct
12	Correct	2 ms	7772 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7512 KB	Output is correct
2	Correct	2 ms	7516 KB	Output is correct
3	Correct	2 ms	7516 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7328 KB	Output is correct
6	Correct	3 ms	7772 KB	Output is correct
7	Correct	2 ms	7516 KB	Output is correct
8	Correct	2 ms	7860 KB	Output is correct
9	Correct	2 ms	7260 KB	Output is correct
10	Correct	2 ms	7588 KB	Output is correct
11	Correct	2 ms	7768 KB	Output is correct
12	Correct	2 ms	7772 KB	Output is correct
13	Correct	4 ms	8540 KB	Output is correct
14	Correct	5 ms	9820 KB	Output is correct
15	Correct	6 ms	11100 KB	Output is correct
16	Correct	7 ms	12380 KB	Output is correct
17	Correct	4 ms	8484 KB	Output is correct
18	Correct	5 ms	9820 KB	Output is correct
19	Correct	6 ms	11032 KB	Output is correct
20	Correct	8 ms	12780 KB	Output is correct
21	Correct	4 ms	8640 KB	Output is correct
22	Correct	5 ms	9820 KB	Output is correct
23	Correct	6 ms	11100 KB	Output is correct
24	Correct	7 ms	12120 KB	Output is correct

Subtask #3
33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	589 ms	125764 KB	Output is correct
2	Correct	885 ms	231732 KB	Output is correct
3	Correct	1194 ms	332588 KB	Output is correct
4	Correct	1479 ms	434616 KB	Output is correct
5	Correct	536 ms	123676 KB	Output is correct
6	Correct	915 ms	226956 KB	Output is correct
7	Correct	1376 ms	326476 KB	Output is correct
8	Correct	1823 ms	426000 KB	Output is correct
9	Correct	528 ms	122976 KB	Output is correct
10	Correct	884 ms	228140 KB	Output is correct
11	Correct	1227 ms	328836 KB	Output is correct
12	Correct	1594 ms	427832 KB	Output is correct

Subtask #4
44.0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7512 KB	Output is correct
2	Correct	2 ms	7516 KB	Output is correct
3	Correct	2 ms	7516 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7328 KB	Output is correct
6	Correct	3 ms	7772 KB	Output is correct
7	Correct	2 ms	7516 KB	Output is correct
8	Correct	2 ms	7860 KB	Output is correct
9	Correct	2 ms	7260 KB	Output is correct
10	Correct	2 ms	7588 KB	Output is correct
11	Correct	2 ms	7768 KB	Output is correct
12	Correct	2 ms	7772 KB	Output is correct
13	Correct	4 ms	8540 KB	Output is correct
14	Correct	5 ms	9820 KB	Output is correct
15	Correct	6 ms	11100 KB	Output is correct
16	Correct	7 ms	12380 KB	Output is correct
17	Correct	4 ms	8484 KB	Output is correct
18	Correct	5 ms	9820 KB	Output is correct
19	Correct	6 ms	11032 KB	Output is correct
20	Correct	8 ms	12780 KB	Output is correct
21	Correct	4 ms	8640 KB	Output is correct
22	Correct	5 ms	9820 KB	Output is correct
23	Correct	6 ms	11100 KB	Output is correct
24	Correct	7 ms	12120 KB	Output is correct
25	Correct	589 ms	125764 KB	Output is correct
26	Correct	885 ms	231732 KB	Output is correct
27	Correct	1194 ms	332588 KB	Output is correct
28	Correct	1479 ms	434616 KB	Output is correct
29	Correct	536 ms	123676 KB	Output is correct
30	Correct	915 ms	226956 KB	Output is correct
31	Correct	1376 ms	326476 KB	Output is correct
32	Correct	1823 ms	426000 KB	Output is correct
33	Correct	528 ms	122976 KB	Output is correct
34	Correct	884 ms	228140 KB	Output is correct
35	Correct	1227 ms	328836 KB	Output is correct
36	Correct	1594 ms	427832 KB	Output is correct
37	Correct	969 ms	126312 KB	Output is correct
38	Correct	1403 ms	231008 KB	Output is correct
39	Correct	1663 ms	335468 KB	Output is correct
40	Correct	1772 ms	435380 KB	Output is correct
41	Correct	961 ms	123892 KB	Output is correct
42	Correct	1431 ms	227176 KB	Output is correct
43	Correct	1766 ms	326972 KB	Output is correct
44	Correct	2069 ms	425348 KB	Output is correct
45	Correct	1105 ms	123324 KB	Output is correct
46	Correct	1667 ms	227968 KB	Output is correct
47	Correct	1818 ms	328040 KB	Output is correct
48	Correct	1906 ms	427872 KB	Output is correct

Submission #855909

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 22.0 / 22.0

Subtask #3 33.0 / 33.0

Subtask #4 44.0 / 44.0

Subtask #1
11.0 / 11.0

Subtask #2
22.0 / 22.0

Subtask #3
33.0 / 33.0

Subtask #4
44.0 / 44.0