oj.uz

Submission #650184

# Submission time Handle Problem Language Result Execution time Memory
650184 2022-10-12T16:38:38 Z Elias_Obeid Klasika (COCI20_klasika) C++17
33 / 110
 705 ms 524288 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 * MAXB> 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 153 ms 333780 KB Output is correct
2 Correct 152 ms 333792 KB Output is correct
3 Correct 154 ms 333924 KB Output is correct
4 Correct 156 ms 333964 KB Output is correct
5 Correct 164 ms 333916 KB Output is correct
6 Correct 153 ms 333856 KB Output is correct
7 Correct 164 ms 333972 KB Output is correct
8 Correct 149 ms 333892 KB Output is correct
9 Correct 162 ms 333916 KB Output is correct
10 Correct 149 ms 333900 KB Output is correct
11 Correct 150 ms 333916 KB Output is correct
12 Correct 170 ms 333932 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 333780 KB Output is correct
2 Correct 152 ms 333792 KB Output is correct
3 Correct 154 ms 333924 KB Output is correct
4 Correct 156 ms 333964 KB Output is correct
5 Correct 164 ms 333916 KB Output is correct
6 Correct 153 ms 333856 KB Output is correct
7 Correct 164 ms 333972 KB Output is correct
8 Correct 149 ms 333892 KB Output is correct
9 Correct 162 ms 333916 KB Output is correct
10 Correct 149 ms 333900 KB Output is correct
11 Correct 150 ms 333916 KB Output is correct
12 Correct 170 ms 333932 KB Output is correct
13 Correct 162 ms 334416 KB Output is correct
14 Correct 154 ms 335060 KB Output is correct
15 Correct 162 ms 335592 KB Output is correct
16 Correct 163 ms 336184 KB Output is correct
17 Correct 150 ms 334268 KB Output is correct
18 Correct 173 ms 335088 KB Output is correct
19 Correct 169 ms 335484 KB Output is correct
20 Correct 157 ms 336056 KB Output is correct
21 Correct 162 ms 334400 KB Output is correct
22 Correct 161 ms 334964 KB Output is correct
23 Correct 159 ms 335612 KB Output is correct
24 Correct 174 ms 336180 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 705 ms 524288 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 153 ms 333780 KB Output is correct
2 Correct 152 ms 333792 KB Output is correct
3 Correct 154 ms 333924 KB Output is correct
4 Correct 156 ms 333964 KB Output is correct
5 Correct 164 ms 333916 KB Output is correct
6 Correct 153 ms 333856 KB Output is correct
7 Correct 164 ms 333972 KB Output is correct
8 Correct 149 ms 333892 KB Output is correct
9 Correct 162 ms 333916 KB Output is correct
10 Correct 149 ms 333900 KB Output is correct
11 Correct 150 ms 333916 KB Output is correct
12 Correct 170 ms 333932 KB Output is correct
13 Correct 162 ms 334416 KB Output is correct
14 Correct 154 ms 335060 KB Output is correct
15 Correct 162 ms 335592 KB Output is correct
16 Correct 163 ms 336184 KB Output is correct
17 Correct 150 ms 334268 KB Output is correct
18 Correct 173 ms 335088 KB Output is correct
19 Correct 169 ms 335484 KB Output is correct
20 Correct 157 ms 336056 KB Output is correct
21 Correct 162 ms 334400 KB Output is correct
22 Correct 161 ms 334964 KB Output is correct
23 Correct 159 ms 335612 KB Output is correct
24 Correct 174 ms 336180 KB Output is correct
25 Runtime error 705 ms 524288 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -