#include <bits/stdc++.h>
using namespace std;
using int32 = int_fast32_t;
const int32 MAXN = 200'000;
int32 timer = 0;
array<vector<pair<int32, int32>>, MAXN + 1> graph;
array<int32, MAXN + 1> xor_depths, time_in, time_out;
void depthFirstSearch(int32 node, int32 current_depth)
{
time_in.at(node) = timer++;
xor_depths.at(node) = current_depth;
for (const auto &[neighbour, weight] : graph.at(node))
{
depthFirstSearch(neighbour, current_depth ^ weight);
}
time_out.at(node) = timer;
}
const int32 BITS = 2;
const int32 MAXB = 30;
struct TrieNode
{
array<int32, BITS> next_nodes;
set<int32> available_positions;
TrieNode()
{
next_nodes.fill(-1);
}
bool inRange(int32 range_start, int32 range_end)
{
auto it = available_positions.lower_bound(range_start);
return (it != available_positions.end() && *it <= range_end);
}
};
int32 current_trie_node = 0;
array<TrieNode, MAXN + 1> trie;
int32 fetchNode()
{
trie.at(current_trie_node) = TrieNode();
return current_trie_node++;
}
const int32 ROOT = fetchNode();
void addNode(int32 graph_node)
{
int32 node = ROOT;
int32 value = xor_depths.at(graph_node);
int32 position = time_in.at(graph_node);
trie.at(node).available_positions.insert(position);
for (int32 bit = MAXB; bit >= 0; --bit)
{
int32 value_bit = (value >> bit & 1);
if (trie.at(node).next_nodes.at(value_bit) == -1)
{
trie.at(node).next_nodes.at(value_bit) = fetchNode();
}
node = trie.at(node).next_nodes.at(value_bit);
trie.at(node).available_positions.insert(position);
}
}
int32 getMaximumXOR(int32 graph_node, int32 range_start, int32 range_end)
{
int32 answer = 0;
int32 node = ROOT;
int32 value = xor_depths.at(graph_node);
for (int32 bit = MAXB; bit >= 0; --bit)
{
if (node == -1)
{
return -1;
}
int32 value_bit = (value >> bit & 1);
if (trie.at(node).next_nodes.at(value_bit ^ 1) != -1 &&
trie.at(trie.at(node).next_nodes.at(value_bit ^ 1)).inRange(range_start, range_end))
{
answer |= (1 << bit);
node = trie.at(node).next_nodes.at(value_bit ^ 1);
}
else
{
node = trie.at(node).next_nodes.at(value_bit);
}
}
return answer;
}
int32 current_graph_node = 1;
int32 main()
{
int32 queries_count;
cin >> queries_count;
vector<array<int32, 3>> queries;
for (int32 query_index = 0; query_index < queries_count; ++query_index)
{
string operation;
cin >> operation;
if (operation == "Query")
{
int32 starting_node, ending_subtree_node;
cin >> starting_node >> ending_subtree_node;
queries.push_back(array<int32, 3>{0, starting_node, ending_subtree_node});
}
else
{
int32 parent_node, weight;
cin >> parent_node >> weight;
graph.at(parent_node).emplace_back(++current_graph_node, weight);
queries.push_back(array<int32, 3>{1, current_graph_node, -1});
}
}
depthFirstSearch(1, 0);
for (int32 query_index = 0; query_index < queries_count; ++query_index)
{
if (queries.at(query_index).at(0) == 1)
{
auto [query_type, node, _] = queries.at(query_index);
addNode(node);
}
else
{
auto [query_type, starting_node, ending_subtree_node] = queries.at(query_index);
int32 range_start = time_in.at(ending_subtree_node);
int32 range_end = time_out.at(ending_subtree_node);
cout << getMaximumXOR(starting_node, range_start, range_end) << "\n";
}
}
return 0;
}
Compilation message
klasika.cpp:101:1: error: '::main' must return 'int'
101 | int32 main()
| ^~~~~
