oj.uz

답안 #650182

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
650182 2022-10-12T16:36:31 Z Elias_Obeid Klasika (COCI20_klasika) C++17
33 / 110
 626 ms 184376 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()
{
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 39508 KB Output is correct
2 Correct 19 ms 39520 KB Output is correct
3 Correct 19 ms 39636 KB Output is correct
4 Correct 18 ms 39624 KB Output is correct
5 Correct 20 ms 39460 KB Output is correct
6 Correct 22 ms 39564 KB Output is correct
7 Correct 23 ms 39636 KB Output is correct
8 Correct 23 ms 39704 KB Output is correct
9 Correct 19 ms 39504 KB Output is correct
10 Correct 18 ms 39524 KB Output is correct
11 Correct 19 ms 39636 KB Output is correct
12 Correct 19 ms 39636 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 39508 KB Output is correct
2 Correct 19 ms 39520 KB Output is correct
3 Correct 19 ms 39636 KB Output is correct
4 Correct 18 ms 39624 KB Output is correct
5 Correct 20 ms 39460 KB Output is correct
6 Correct 22 ms 39564 KB Output is correct
7 Correct 23 ms 39636 KB Output is correct
8 Correct 23 ms 39704 KB Output is correct
9 Correct 19 ms 39504 KB Output is correct
10 Correct 18 ms 39524 KB Output is correct
11 Correct 19 ms 39636 KB Output is correct
12 Correct 19 ms 39636 KB Output is correct
13 Correct 22 ms 40024 KB Output is correct
14 Correct 23 ms 40660 KB Output is correct
15 Correct 25 ms 41408 KB Output is correct
16 Correct 26 ms 41932 KB Output is correct
17 Correct 22 ms 40056 KB Output is correct
18 Correct 24 ms 40660 KB Output is correct
19 Correct 26 ms 41284 KB Output is correct
20 Correct 26 ms 41836 KB Output is correct
21 Correct 24 ms 40020 KB Output is correct
22 Correct 27 ms 40652 KB Output is correct
23 Correct 25 ms 41268 KB Output is correct
24 Correct 27 ms 41812 KB Output is correct

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 626 ms 184376 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 39508 KB Output is correct
2 Correct 19 ms 39520 KB Output is correct
3 Correct 19 ms 39636 KB Output is correct
4 Correct 18 ms 39624 KB Output is correct
5 Correct 20 ms 39460 KB Output is correct
6 Correct 22 ms 39564 KB Output is correct
7 Correct 23 ms 39636 KB Output is correct
8 Correct 23 ms 39704 KB Output is correct
9 Correct 19 ms 39504 KB Output is correct
10 Correct 18 ms 39524 KB Output is correct
11 Correct 19 ms 39636 KB Output is correct
12 Correct 19 ms 39636 KB Output is correct
13 Correct 22 ms 40024 KB Output is correct
14 Correct 23 ms 40660 KB Output is correct
15 Correct 25 ms 41408 KB Output is correct
16 Correct 26 ms 41932 KB Output is correct
17 Correct 22 ms 40056 KB Output is correct
18 Correct 24 ms 40660 KB Output is correct
19 Correct 26 ms 41284 KB Output is correct
20 Correct 26 ms 41836 KB Output is correct
21 Correct 24 ms 40020 KB Output is correct
22 Correct 27 ms 40652 KB Output is correct
23 Correct 25 ms 41268 KB Output is correct
24 Correct 27 ms 41812 KB Output is correct
25 Runtime error 626 ms 184376 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -