oj.uz

Submission #1093034

# Submission time Handle Problem Language Result Execution time Memory
1093034 2024-09-25T18:10:27 Z Hacv16 Klasika (COCI20_klasika) C++17
33 / 110
 854 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX = 2e5 + 15;
const int LOG = 31;

int n = 1, q, x[MAX];
int timer, tin[MAX], tout[MAX];

vector<int> adj[MAX];

struct Trie
{
	int numNodes;
	vector<array<int, 2>> trie;

	int create()
	{
		trie.push_back({ 0, 0 });
		return numNodes++;
	}

	Trie(void){ numNodes = 0; create(); }

	void add(int x)
	{
		int cur = 0;

		for(int i = LOG - 1; i >= 0; i--)
		{
			bool id = (x & (1 << i));
 
			if(trie[cur][id] == 0)
			{
				int newNode = create();
				trie[cur][id] = newNode;
			}
 
			cur = trie[cur][id];
		}
	}

	int query(int x)
	{
		int cur = 0, resp = 0;

		for(int i = LOG - 1; i >= 0; i--)
		{
			bool id = (x & (1 << i));

			if(trie[cur][!id] != 0)
			{
				resp ^= (1 << i);
				cur = trie[cur][!id];

			} else cur = trie[cur][id];
		}

		return resp;
	}
} seg[4 * MAX];

void dfs(int u, int p)
{
	tin[u] = ++timer;

	for(auto v : adj[u])
	{
		if(v == p) continue;
		dfs(v, u);
	}

	tout[u] = timer;
}

void update(int i, int val, int p, int l, int r)
{
    if(i < l || i > r) return;
    if(l == r)
    {
        seg[p].add(val); 
        return;
    }
    
    int m = (l + r) >> 1, e = 2 * p, d = e + 1;
    update(i, val, e, l, m); update(i, val, d, m + 1, r);
    
    seg[p].add(val);
}

int query(int a, int b, int val, int p, int l, int r)
{
	if(a > r || b < l) return -1;
	if(a <= l && r <= b) return seg[p].query(val);

	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
	return max(query(a, b, val, e, l, m), query(a, b, val, d, m + 1, r));
}

int32_t main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> q;

	vector<tuple<int, int, int>> events;

	events.emplace_back(1, 1, x[1]);

	while(q--)
	{
		string op; cin >> op;

		if(op == "Add")
		{
			int p, w; cin >> p >> w;
			int newNode = ++n;

			x[newNode] = x[p] ^ w;

			adj[p].push_back(newNode);
			adj[newNode].push_back(p);

			events.emplace_back(1, newNode, x[newNode]);

		}else{
			int a, b; cin >> a >> b;
			events.emplace_back(2, x[a], b);
		}
	}

	dfs(1, 1);

	for(int i = 1; i < min(4 * n + 10, 4 * MAX); i++) seg[i] = Trie();

	for(auto [type, x, y] : events)
	{
		if(type == 1) update(tin[x], y, 1, 1, n);
		else cout << query(tin[y], tout[y], x, 1, 1, n) << '\n';
	}

	cout << '\n';
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 55376 KB Output is correct
2 Correct 50 ms 55376 KB Output is correct
3 Correct 54 ms 55520 KB Output is correct
4 Correct 58 ms 55632 KB Output is correct
5 Correct 62 ms 55356 KB Output is correct
6 Correct 52 ms 55384 KB Output is correct
7 Correct 52 ms 55376 KB Output is correct
8 Correct 49 ms 55640 KB Output is correct
9 Correct 52 ms 55384 KB Output is correct
10 Correct 53 ms 55388 KB Output is correct
11 Correct 52 ms 55380 KB Output is correct
12 Correct 50 ms 55576 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 55376 KB Output is correct
2 Correct 50 ms 55376 KB Output is correct
3 Correct 54 ms 55520 KB Output is correct
4 Correct 58 ms 55632 KB Output is correct
5 Correct 62 ms 55356 KB Output is correct
6 Correct 52 ms 55384 KB Output is correct
7 Correct 52 ms 55376 KB Output is correct
8 Correct 49 ms 55640 KB Output is correct
9 Correct 52 ms 55384 KB Output is correct
10 Correct 53 ms 55388 KB Output is correct
11 Correct 52 ms 55380 KB Output is correct
12 Correct 50 ms 55576 KB Output is correct
13 Correct 52 ms 56404 KB Output is correct
14 Correct 56 ms 57552 KB Output is correct
15 Correct 54 ms 58828 KB Output is correct
16 Correct 68 ms 60492 KB Output is correct
17 Correct 51 ms 56404 KB Output is correct
18 Correct 56 ms 57684 KB Output is correct
19 Correct 55 ms 58708 KB Output is correct
20 Correct 57 ms 60372 KB Output is correct
21 Correct 54 ms 56404 KB Output is correct
22 Correct 55 ms 57680 KB Output is correct
23 Correct 58 ms 58576 KB Output is correct
24 Correct 58 ms 60232 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 206156 KB Output is correct
2 Correct 548 ms 366012 KB Output is correct
3 Correct 854 ms 516508 KB Output is correct
4 Runtime error 724 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 55376 KB Output is correct
2 Correct 50 ms 55376 KB Output is correct
3 Correct 54 ms 55520 KB Output is correct
4 Correct 58 ms 55632 KB Output is correct
5 Correct 62 ms 55356 KB Output is correct
6 Correct 52 ms 55384 KB Output is correct
7 Correct 52 ms 55376 KB Output is correct
8 Correct 49 ms 55640 KB Output is correct
9 Correct 52 ms 55384 KB Output is correct
10 Correct 53 ms 55388 KB Output is correct
11 Correct 52 ms 55380 KB Output is correct
12 Correct 50 ms 55576 KB Output is correct
13 Correct 52 ms 56404 KB Output is correct
14 Correct 56 ms 57552 KB Output is correct
15 Correct 54 ms 58828 KB Output is correct
16 Correct 68 ms 60492 KB Output is correct
17 Correct 51 ms 56404 KB Output is correct
18 Correct 56 ms 57684 KB Output is correct
19 Correct 55 ms 58708 KB Output is correct
20 Correct 57 ms 60372 KB Output is correct
21 Correct 54 ms 56404 KB Output is correct
22 Correct 55 ms 57680 KB Output is correct
23 Correct 58 ms 58576 KB Output is correct
24 Correct 58 ms 60232 KB Output is correct
25 Correct 316 ms 206156 KB Output is correct
26 Correct 548 ms 366012 KB Output is correct
27 Correct 854 ms 516508 KB Output is correct
28 Runtime error 724 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -