oj.uz

Submission #650180

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

const int32_t MAXN = 500'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);
    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 20 ms 39508 KB Output is correct
2 Correct 20 ms 39580 KB Output is correct
3 Correct 19 ms 39568 KB Output is correct
4 Correct 21 ms 39704 KB Output is correct
5 Correct 20 ms 39528 KB Output is correct
6 Correct 19 ms 39576 KB Output is correct
7 Correct 20 ms 39576 KB Output is correct
8 Correct 20 ms 39708 KB Output is correct
9 Correct 20 ms 39520 KB Output is correct
10 Correct 19 ms 39508 KB Output is correct
11 Correct 20 ms 39712 KB Output is correct
12 Correct 19 ms 39636 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 39508 KB Output is correct
2 Correct 20 ms 39580 KB Output is correct
3 Correct 19 ms 39568 KB Output is correct
4 Correct 21 ms 39704 KB Output is correct
5 Correct 20 ms 39528 KB Output is correct
6 Correct 19 ms 39576 KB Output is correct
7 Correct 20 ms 39576 KB Output is correct
8 Correct 20 ms 39708 KB Output is correct
9 Correct 20 ms 39520 KB Output is correct
10 Correct 19 ms 39508 KB Output is correct
11 Correct 20 ms 39712 KB Output is correct
12 Correct 19 ms 39636 KB Output is correct
13 Correct 22 ms 40148 KB Output is correct
14 Correct 24 ms 40788 KB Output is correct
15 Correct 25 ms 41428 KB Output is correct
16 Correct 25 ms 41888 KB Output is correct
17 Correct 23 ms 40020 KB Output is correct
18 Correct 24 ms 40616 KB Output is correct
19 Correct 26 ms 41256 KB Output is correct
20 Correct 28 ms 41892 KB Output is correct
21 Correct 22 ms 40020 KB Output is correct
22 Correct 24 ms 40724 KB Output is correct
23 Correct 24 ms 41324 KB Output is correct
24 Correct 26 ms 41840 KB Output is correct

Subtask #3
0 / 33.0

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

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 39508 KB Output is correct
2 Correct 20 ms 39580 KB Output is correct
3 Correct 19 ms 39568 KB Output is correct
4 Correct 21 ms 39704 KB Output is correct
5 Correct 20 ms 39528 KB Output is correct
6 Correct 19 ms 39576 KB Output is correct
7 Correct 20 ms 39576 KB Output is correct
8 Correct 20 ms 39708 KB Output is correct
9 Correct 20 ms 39520 KB Output is correct
10 Correct 19 ms 39508 KB Output is correct
11 Correct 20 ms 39712 KB Output is correct
12 Correct 19 ms 39636 KB Output is correct
13 Correct 22 ms 40148 KB Output is correct
14 Correct 24 ms 40788 KB Output is correct
15 Correct 25 ms 41428 KB Output is correct
16 Correct 25 ms 41888 KB Output is correct
17 Correct 23 ms 40020 KB Output is correct
18 Correct 24 ms 40616 KB Output is correct
19 Correct 26 ms 41256 KB Output is correct
20 Correct 28 ms 41892 KB Output is correct
21 Correct 22 ms 40020 KB Output is correct
22 Correct 24 ms 40724 KB Output is correct
23 Correct 24 ms 41324 KB Output is correct
24 Correct 26 ms 41840 KB Output is correct
25 Runtime error 560 ms 184444 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -