oj.uz

Submission #1093040

# Submission time Handle Problem Language Result Execution time Memory
1093040 2024-09-25T18:17:00 Z Hacv16 Klasika (COCI20_klasika) C++17
33 / 110
 698 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
 
const int MAX = 3e5 + 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 build(int p, int l, int r)
{
	seg[p] = Trie();

	if(l == r) return;

	int m = (l + r) >> 1, e = 2 * p, d = e + 1; 
	build(e, l, m); build(d, m + 1, r);
}

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);
	build(1, 1, n);
 
	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 84 ms 82776 KB Output is correct
2 Correct 66 ms 82648 KB Output is correct
3 Correct 80 ms 82768 KB Output is correct
4 Correct 79 ms 83028 KB Output is correct
5 Correct 78 ms 82748 KB Output is correct
6 Correct 82 ms 82768 KB Output is correct
7 Correct 93 ms 82772 KB Output is correct
8 Correct 82 ms 83028 KB Output is correct
9 Correct 82 ms 82768 KB Output is correct
10 Correct 79 ms 82772 KB Output is correct
11 Correct 87 ms 82768 KB Output is correct
12 Correct 81 ms 83028 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 82776 KB Output is correct
2 Correct 66 ms 82648 KB Output is correct
3 Correct 80 ms 82768 KB Output is correct
4 Correct 79 ms 83028 KB Output is correct
5 Correct 78 ms 82748 KB Output is correct
6 Correct 82 ms 82768 KB Output is correct
7 Correct 93 ms 82772 KB Output is correct
8 Correct 82 ms 83028 KB Output is correct
9 Correct 82 ms 82768 KB Output is correct
10 Correct 79 ms 82772 KB Output is correct
11 Correct 87 ms 82768 KB Output is correct
12 Correct 81 ms 83028 KB Output is correct
13 Correct 87 ms 83792 KB Output is correct
14 Correct 84 ms 85060 KB Output is correct
15 Correct 85 ms 86224 KB Output is correct
16 Correct 89 ms 87884 KB Output is correct
17 Correct 83 ms 83684 KB Output is correct
18 Correct 84 ms 85072 KB Output is correct
19 Correct 87 ms 86096 KB Output is correct
20 Correct 89 ms 87760 KB Output is correct
21 Correct 85 ms 83736 KB Output is correct
22 Correct 86 ms 85076 KB Output is correct
23 Correct 85 ms 86220 KB Output is correct
24 Correct 87 ms 87628 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 236064 KB Output is correct
2 Correct 592 ms 395216 KB Output is correct
3 Runtime error 698 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 82776 KB Output is correct
2 Correct 66 ms 82648 KB Output is correct
3 Correct 80 ms 82768 KB Output is correct
4 Correct 79 ms 83028 KB Output is correct
5 Correct 78 ms 82748 KB Output is correct
6 Correct 82 ms 82768 KB Output is correct
7 Correct 93 ms 82772 KB Output is correct
8 Correct 82 ms 83028 KB Output is correct
9 Correct 82 ms 82768 KB Output is correct
10 Correct 79 ms 82772 KB Output is correct
11 Correct 87 ms 82768 KB Output is correct
12 Correct 81 ms 83028 KB Output is correct
13 Correct 87 ms 83792 KB Output is correct
14 Correct 84 ms 85060 KB Output is correct
15 Correct 85 ms 86224 KB Output is correct
16 Correct 89 ms 87884 KB Output is correct
17 Correct 83 ms 83684 KB Output is correct
18 Correct 84 ms 85072 KB Output is correct
19 Correct 87 ms 86096 KB Output is correct
20 Correct 89 ms 87760 KB Output is correct
21 Correct 85 ms 83736 KB Output is correct
22 Correct 86 ms 85076 KB Output is correct
23 Correct 85 ms 86220 KB Output is correct
24 Correct 87 ms 87628 KB Output is correct
25 Correct 347 ms 236064 KB Output is correct
26 Correct 592 ms 395216 KB Output is correct
27 Runtime error 698 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -