oj.uz

Submission #650183

# Submission time Handle Problem Language Result Execution time Memory
650183 2022-10-12T16:37:31 Z Elias_Obeid Klasika (COCI20_klasika) C++17
33 / 110
 2021 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

const int32_t MAXN = 2'000'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()
{
    assert(current_trie_node <= MAXN);
    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);
    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 answer;
        }

        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);

    addNode(1);
    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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 156892 KB Output is correct
2 Correct 73 ms 156948 KB Output is correct
3 Correct 72 ms 156980 KB Output is correct
4 Correct 81 ms 157088 KB Output is correct
5 Correct 73 ms 156896 KB Output is correct
6 Correct 74 ms 156980 KB Output is correct
7 Correct 72 ms 157012 KB Output is correct
8 Correct 73 ms 157004 KB Output is correct
9 Correct 71 ms 156912 KB Output is correct
10 Correct 75 ms 156920 KB Output is correct
11 Correct 77 ms 157040 KB Output is correct
12 Correct 71 ms 157084 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 156892 KB Output is correct
2 Correct 73 ms 156948 KB Output is correct
3 Correct 72 ms 156980 KB Output is correct
4 Correct 81 ms 157088 KB Output is correct
5 Correct 73 ms 156896 KB Output is correct
6 Correct 74 ms 156980 KB Output is correct
7 Correct 72 ms 157012 KB Output is correct
8 Correct 73 ms 157004 KB Output is correct
9 Correct 71 ms 156912 KB Output is correct
10 Correct 75 ms 156920 KB Output is correct
11 Correct 77 ms 157040 KB Output is correct
12 Correct 71 ms 157084 KB Output is correct
13 Correct 76 ms 157516 KB Output is correct
14 Correct 79 ms 158128 KB Output is correct
15 Correct 78 ms 158680 KB Output is correct
16 Correct 79 ms 159332 KB Output is correct
17 Correct 79 ms 157488 KB Output is correct
18 Correct 79 ms 158092 KB Output is correct
19 Correct 77 ms 158672 KB Output is correct
20 Correct 78 ms 159244 KB Output is correct
21 Correct 76 ms 157504 KB Output is correct
22 Correct 80 ms 158204 KB Output is correct
23 Correct 76 ms 158604 KB Output is correct
24 Correct 80 ms 159260 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 751 ms 222480 KB Output is correct
2 Correct 1213 ms 287348 KB Output is correct
3 Correct 1659 ms 348188 KB Output is correct
4 Runtime error 2021 ms 524288 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 156892 KB Output is correct
2 Correct 73 ms 156948 KB Output is correct
3 Correct 72 ms 156980 KB Output is correct
4 Correct 81 ms 157088 KB Output is correct
5 Correct 73 ms 156896 KB Output is correct
6 Correct 74 ms 156980 KB Output is correct
7 Correct 72 ms 157012 KB Output is correct
8 Correct 73 ms 157004 KB Output is correct
9 Correct 71 ms 156912 KB Output is correct
10 Correct 75 ms 156920 KB Output is correct
11 Correct 77 ms 157040 KB Output is correct
12 Correct 71 ms 157084 KB Output is correct
13 Correct 76 ms 157516 KB Output is correct
14 Correct 79 ms 158128 KB Output is correct
15 Correct 78 ms 158680 KB Output is correct
16 Correct 79 ms 159332 KB Output is correct
17 Correct 79 ms 157488 KB Output is correct
18 Correct 79 ms 158092 KB Output is correct
19 Correct 77 ms 158672 KB Output is correct
20 Correct 78 ms 159244 KB Output is correct
21 Correct 76 ms 157504 KB Output is correct
22 Correct 80 ms 158204 KB Output is correct
23 Correct 76 ms 158604 KB Output is correct
24 Correct 80 ms 159260 KB Output is correct
25 Correct 751 ms 222480 KB Output is correct
26 Correct 1213 ms 287348 KB Output is correct
27 Correct 1659 ms 348188 KB Output is correct
28 Runtime error 2021 ms 524288 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -