oj.uz

Submission #1093049

# Submission time Handle Problem Language Result Execution time Memory
1093049 2024-09-25T18:43:10 Z Hacv16 Klasika (COCI20_klasika) C++17
33 / 110
 751 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], node[MAX];
bool active[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)
{
	if(r - l + 1 >= 32) 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)
	{
	    int ret = 0;
	    
	    if(r - l + 1 < 32)
	    {
	        for(int i = l; i <= r; i++)
	            if(active[node[i]]) ret = max(ret, (x[ node[i] ] ^ val));
	            
	        return ret;
	    }
	    
	    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(int i = 1; i <= n; i++)
        node[ tin[i] ] = i;
 
	for(auto [type, x, y] : events)
	{
		if(type == 1) update(tin[x], y, 1, 1, n), active[x] = true;
		else cout << query(tin[y], tout[y], x, 1, 1, n) << '\n';
	}
 
	cout << '\n';
}

Compilation message

klasika.cpp: In function 'int32_t main()':
klasika.cpp:164:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  164 |     for(int i = 1; i <= n; i++)
      |     ^~~
klasika.cpp:167:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  167 |  for(auto [type, x, y] : events)
      |  ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 82772 KB Output is correct
2 Correct 68 ms 82768 KB Output is correct
3 Correct 81 ms 82772 KB Output is correct
4 Correct 81 ms 83024 KB Output is correct
5 Correct 78 ms 82564 KB Output is correct
6 Correct 80 ms 82772 KB Output is correct
7 Correct 84 ms 82768 KB Output is correct
8 Correct 78 ms 83028 KB Output is correct
9 Correct 81 ms 82784 KB Output is correct
10 Correct 81 ms 82768 KB Output is correct
11 Correct 80 ms 82896 KB Output is correct
12 Correct 86 ms 83024 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 82772 KB Output is correct
2 Correct 68 ms 82768 KB Output is correct
3 Correct 81 ms 82772 KB Output is correct
4 Correct 81 ms 83024 KB Output is correct
5 Correct 78 ms 82564 KB Output is correct
6 Correct 80 ms 82772 KB Output is correct
7 Correct 84 ms 82768 KB Output is correct
8 Correct 78 ms 83028 KB Output is correct
9 Correct 81 ms 82784 KB Output is correct
10 Correct 81 ms 82768 KB Output is correct
11 Correct 80 ms 82896 KB Output is correct
12 Correct 86 ms 83024 KB Output is correct
13 Correct 78 ms 83852 KB Output is correct
14 Correct 81 ms 85168 KB Output is correct
15 Correct 80 ms 86336 KB Output is correct
16 Correct 89 ms 87984 KB Output is correct
17 Correct 82 ms 83792 KB Output is correct
18 Correct 81 ms 85072 KB Output is correct
19 Correct 88 ms 86036 KB Output is correct
20 Correct 97 ms 87752 KB Output is correct
21 Correct 80 ms 83864 KB Output is correct
22 Correct 88 ms 85076 KB Output is correct
23 Correct 92 ms 86224 KB Output is correct
24 Correct 93 ms 87768 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 235912 KB Output is correct
2 Correct 602 ms 395732 KB Output is correct
3 Runtime error 751 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 86 ms 82772 KB Output is correct
2 Correct 68 ms 82768 KB Output is correct
3 Correct 81 ms 82772 KB Output is correct
4 Correct 81 ms 83024 KB Output is correct
5 Correct 78 ms 82564 KB Output is correct
6 Correct 80 ms 82772 KB Output is correct
7 Correct 84 ms 82768 KB Output is correct
8 Correct 78 ms 83028 KB Output is correct
9 Correct 81 ms 82784 KB Output is correct
10 Correct 81 ms 82768 KB Output is correct
11 Correct 80 ms 82896 KB Output is correct
12 Correct 86 ms 83024 KB Output is correct
13 Correct 78 ms 83852 KB Output is correct
14 Correct 81 ms 85168 KB Output is correct
15 Correct 80 ms 86336 KB Output is correct
16 Correct 89 ms 87984 KB Output is correct
17 Correct 82 ms 83792 KB Output is correct
18 Correct 81 ms 85072 KB Output is correct
19 Correct 88 ms 86036 KB Output is correct
20 Correct 97 ms 87752 KB Output is correct
21 Correct 80 ms 83864 KB Output is correct
22 Correct 88 ms 85076 KB Output is correct
23 Correct 92 ms 86224 KB Output is correct
24 Correct 93 ms 87768 KB Output is correct
25 Correct 436 ms 235912 KB Output is correct
26 Correct 602 ms 395732 KB Output is correct
27 Runtime error 751 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -