Submission #650176

#	Time	Username	Problem	Language	Result	Execution time	Memory
650176		Elias_Obeid	Klasika (COCI20_klasika)	C++17	0 / 110	276 ms	79276 KiB

klasika

#include <bits/stdc++.h>
using namespace std;

const int32_t MAXN = 200'000;

int32_t timer = 0;
array<vector<pair<int32_t, int32_t>>, MAXN + 1> graph;
array<int32_t, MAXN + 1> xor_depths, time_in, time_out;

void depthFirstSearch(int32_t node, int32_t 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_t BITS = 2;
const int32_t MAXB = 30;

struct TrieNode
{
    array<int32_t, BITS> next_nodes;
    set<int32_t> available_positions;

    TrieNode()
    {
        next_nodes.fill(-1);
    }

    bool inRange(int32_t range_start, int32_t range_end)
    {
        auto it = available_positions.lower_bound(range_start);
        return (it != available_positions.end() && *it <= range_end);
    }
};

int32_t current_trie_node = 0;
array<TrieNode, MAXN + 1> trie;

int32_t fetchNode()
{
    trie.at(current_trie_node) = TrieNode();
    return current_trie_node++;
}

const int32_t ROOT = fetchNode();

void addNode(int32_t graph_node)
{
    int32_t node = ROOT;
    int32_t value = xor_depths.at(graph_node);
    int32_t position = time_in.at(graph_node);
    trie.at(node).available_positions.insert(position);
    for (int32_t bit = MAXB; bit >= 0; --bit)
    {
        int32_t 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_t getMaximumXOR(int32_t graph_node, int32_t range_start, int32_t range_end)
{
    int32_t answer = 0;
    int32_t node = ROOT;
    int32_t value = xor_depths.at(graph_node);
    for (int32_t bit = MAXB; bit >= 0; --bit)
    {
        if (node == -1)
        {
            return -1;
        }

        int32_t 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_t current_graph_node = 1;

int32_t main()
{
    int32_t queries_count;
    cin >> queries_count;

    vector<array<int32_t, 3>> queries;
    for (int32_t query_index = 0; query_index < queries_count; ++query_index)
    {
        string operation;
        cin >> operation;

        if (operation == "Query")
        {
            int32_t starting_node, ending_subtree_node;
            cin >> starting_node >> ending_subtree_node;
            queries.push_back(array<int32_t, 3>{0, starting_node, ending_subtree_node});
        }
        else
        {
            int32_t parent_node, weight;
            cin >> parent_node >> weight;
            graph.at(parent_node).emplace_back(++current_graph_node, weight);
            queries.push_back(array<int32_t, 3>{1, current_graph_node, -1});
        }
    }
    depthFirstSearch(1, 0);

    for (int32_t 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_t range_start = time_in.at(ending_subtree_node);
            int32_t range_end = time_out.at(ending_subtree_node);
            cout << getMaximumXOR(starting_node, range_start, range_end) << "\n";
        }
    }
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44