제출 #1252734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252734		mazen_ghanayem	Klasika (COCI20_klasika)	C++20	0 / 110	5114 ms	497092 KiB

klasika

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

#define nl "\n"

// --- Data Structures for Offline Solution ---

const int BITS = 30;

// Standard, non-persistent Binary Trie for Max XOR queries on a set of numbers.
struct BinaryTrie {
    struct Node {
        Node* children[2];
        int count;
        Node() : count(0), children{nullptr, nullptr} {}
    };

    Node* root;

    BinaryTrie() { root = new Node(); }

    void insert(int val) {
        Node* curr = root;
        for (int i = BITS - 1; i >= 0; --i) {
            curr->count++;
            int bit = (val >> i) & 1;
            if (!curr->children[bit]) {
                curr->children[bit] = new Node();
            }
            curr = curr->children[bit];
        }
        curr->count++;
    }

    int get_max_xor(int val) {
        Node* curr = root;
        int max_xor_val = 0;
        for (int i = BITS - 1; i >= 0; --i) {
            int bit = (val >> i) & 1;
            int required_bit = 1 - bit;
            if (curr->children[required_bit] && curr->children[required_bit]->count > 0) {
                max_xor_val |= (1 << i);
                curr = curr->children[required_bit];
            } else {
                curr = curr->children[bit];
            }
        }
        return max_xor_val;
    }
};

// A Segment Tree where each node contains a Binary Trie.
// This allows for range queries that perform an operation (max_xor) on the aggregated data.
struct SegTreeNode {
    BinaryTrie trie;
};

std::vector<SegTreeNode> seg_tree;
int N_final; // Final number of nodes in the tree

void seg_tree_update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        seg_tree[node].trie.insert(val);
        return;
    }
    seg_tree[node].trie.insert(val);
    int mid = start + (end - start) / 2;
    if (start <= idx && idx <= mid) {
        seg_tree_update(2 * node, start, mid, idx, val);
    } else {
        seg_tree_update(2 * node + 1, mid + 1, end, idx, val);
    }
}

int seg_tree_query(int node, int start, int end, int l, int r, int val) {
    if (r < start || end < l) {
        return 0;
    }
    if (l <= start && end <= r) {
        return seg_tree[node].trie.get_max_xor(val);
    }
    int mid = start + (end - start) / 2;
    int p1 = seg_tree_query(2 * node, start, mid, l, r, val);
    int p2 = seg_tree_query(2 * node + 1, mid + 1, end, l, r, val);
    return std::max(p1, p2);
}


// --- Solver for the "Klasika" Problem (Offline Approach) ---

struct Query {
    int type, time, id;
    int u, v, w; // u,v for query, u,w for add
};

class KlasikaSolver {
private:
    struct Edge {
        int to;
        int weight;
    };
    
    std::vector<std::vector<Edge>> adj;
    std::vector<int> dist, tin, tout, dfs_order_pos, dfs_order_val;
    int timer;

    void dfs_flattener(int u, int p, int current_xor_dist) {
        tin[u] = ++timer;
        dfs_order_pos[u] = timer;
        dfs_order_val[timer] = dist[u] = current_xor_dist;

        for (const auto& edge : adj[u]) {
            int v = edge.to;
            if (v != p) {
                dfs_flattener(v, u, current_xor_dist ^ edge.weight);
            }
        }
        tout[u] = timer;
    }

public:
    void solve() {
        int q;
        std::cin >> q;

        std::vector<Query> queries(q);
        int node_count = 1;
        adj.resize(q + 2);

        for (int i = 0; i < q; ++i) {
            std::string type;
            std::cin >> type;
            queries[i].id = i;
            if (type == "Add") {
                queries[i].type = 1;
                std::cin >> queries[i].u >> queries[i].w;
                node_count++;
                adj[queries[i].u].push_back({node_count, queries[i].w});
                queries[i].time = node_count;
            } else {
                queries[i].type = 2;
                std::cin >> queries[i].u >> queries[i].v;
                queries[i].time = node_count;
            }
        }
        N_final = node_count;

        // Perform one DFS on the final tree
        dist.resize(N_final + 1);
        tin.resize(N_final + 1);
        tout.resize(N_final + 1);
        dfs_order_pos.resize(N_final + 1);
        dfs_order_val.resize(N_final + 1);
        timer = 0;
        dfs_flattener(1, 0, 0);

        // Sort queries by their 'time' (node_count when asked)
        std::sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
            return a.time < b.time;
        });

        std::vector<int> answers(q);
        seg_tree.resize(4 * N_final);
        int current_nodes_in_struct = 0;

        // Process queries and add nodes to the data structure chronologically
        for (const auto& query : queries) {
            while (current_nodes_in_struct < query.time) {
                current_nodes_in_struct++;
                seg_tree_update(1, 1, N_final, dfs_order_pos[current_nodes_in_struct], dist[current_nodes_in_struct]);
            }
            if (query.type == 2) {
                int a = query.u;
                int b = query.v;
                int l = tin[b];
                int r = tout[b];
                answers[query.id] = seg_tree_query(1, 1, N_final, l, r, dist[a]);
            }
        }

        for (int i = 0; i < q; ++i) {
            if (answers[i] != 0 || (answers[i]==0 && queries[i].type==2)) { // Print only for query types
                 bool is_query = false;
                 for(const auto& qr : queries){
                     if(qr.id == i && qr.type == 2){
                         is_query = true;
                         break;
                     }
                 }
                 if(is_query) std::cout << answers[i] << nl;
            }
        }
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    KlasikaSolver solver;
    solver.solve();
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44