oj.uz

Submission #650176

# Submission time Handle Problem Language Result Execution time Memory
650176 2022-10-12T16:30:25 Z Elias_Obeid Klasika (COCI20_klasika) C++17
0 / 110
 276 ms 79276 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 16020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 16020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 276 ms 79276 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 16020 KB Output isn't correct
2 Halted 0 ms 0 KB -