oj.uz

Submission #1093033

# Submission time Handle Problem Language Result Execution time Memory
1093033 2024-09-25T18:09:45 Z Hacv16 Klasika (COCI20_klasika) C++17
33 / 110
 766 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 < 4 * n + 10; 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 55348 KB Output is correct
2 Correct 51 ms 55380 KB Output is correct
3 Correct 51 ms 55376 KB Output is correct
4 Correct 51 ms 55632 KB Output is correct
5 Correct 53 ms 55108 KB Output is correct
6 Correct 51 ms 55380 KB Output is correct
7 Correct 52 ms 55380 KB Output is correct
8 Correct 49 ms 55548 KB Output is correct
9 Correct 47 ms 55128 KB Output is correct
10 Correct 47 ms 55324 KB Output is correct
11 Correct 46 ms 55376 KB Output is correct
12 Correct 47 ms 55632 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 55348 KB Output is correct
2 Correct 51 ms 55380 KB Output is correct
3 Correct 51 ms 55376 KB Output is correct
4 Correct 51 ms 55632 KB Output is correct
5 Correct 53 ms 55108 KB Output is correct
6 Correct 51 ms 55380 KB Output is correct
7 Correct 52 ms 55380 KB Output is correct
8 Correct 49 ms 55548 KB Output is correct
9 Correct 47 ms 55128 KB Output is correct
10 Correct 47 ms 55324 KB Output is correct
11 Correct 46 ms 55376 KB Output is correct
12 Correct 47 ms 55632 KB Output is correct
13 Correct 48 ms 56404 KB Output is correct
14 Correct 51 ms 57692 KB Output is correct
15 Correct 51 ms 58840 KB Output is correct
16 Correct 54 ms 60664 KB Output is correct
17 Correct 49 ms 56400 KB Output is correct
18 Correct 50 ms 57684 KB Output is correct
19 Correct 50 ms 58708 KB Output is correct
20 Correct 68 ms 60396 KB Output is correct
21 Correct 52 ms 56668 KB Output is correct
22 Correct 51 ms 57684 KB Output is correct
23 Correct 50 ms 58840 KB Output is correct
24 Correct 52 ms 60232 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 208864 KB Output is correct
2 Correct 551 ms 369020 KB Output is correct
3 Correct 766 ms 519616 KB Output is correct
4 Runtime error 718 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 55348 KB Output is correct
2 Correct 51 ms 55380 KB Output is correct
3 Correct 51 ms 55376 KB Output is correct
4 Correct 51 ms 55632 KB Output is correct
5 Correct 53 ms 55108 KB Output is correct
6 Correct 51 ms 55380 KB Output is correct
7 Correct 52 ms 55380 KB Output is correct
8 Correct 49 ms 55548 KB Output is correct
9 Correct 47 ms 55128 KB Output is correct
10 Correct 47 ms 55324 KB Output is correct
11 Correct 46 ms 55376 KB Output is correct
12 Correct 47 ms 55632 KB Output is correct
13 Correct 48 ms 56404 KB Output is correct
14 Correct 51 ms 57692 KB Output is correct
15 Correct 51 ms 58840 KB Output is correct
16 Correct 54 ms 60664 KB Output is correct
17 Correct 49 ms 56400 KB Output is correct
18 Correct 50 ms 57684 KB Output is correct
19 Correct 50 ms 58708 KB Output is correct
20 Correct 68 ms 60396 KB Output is correct
21 Correct 52 ms 56668 KB Output is correct
22 Correct 51 ms 57684 KB Output is correct
23 Correct 50 ms 58840 KB Output is correct
24 Correct 52 ms 60232 KB Output is correct
25 Correct 317 ms 208864 KB Output is correct
26 Correct 551 ms 369020 KB Output is correct
27 Correct 766 ms 519616 KB Output is correct
28 Runtime error 718 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -