제출 #1252731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252731		mazen_ghanayem	Klasika (COCI20_klasika)	C++20	33 / 110	5090 ms	10776 KiB

klasika

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

#define nl "\n"

// --- Persistent Binary Trie (Clean Template) ---
// This is a clean, encapsulated C++ implementation based on the logic of the
// accepted competitive programming solution. It uses a pre-allocated node pool
// and integer indices instead of raw pointers to achieve high performance and
// avoid runtime errors.

class PersistentBinaryTrie {
private:
    static const int BITS = 30; // For values up to 2^30

    struct Node {
        int children[2];
        int count;
        Node() : count(0) {
            children[0] = children[1] = 0; // Index 0 is the sentinel null node.
        }
    };

    std::vector<Node> node_pool;
    std::vector<int> roots;
    int node_idx;

    int clone_node(int u) {
        node_pool[node_idx] = node_pool[u];
        return node_idx++;
    }

    int insert_internal(int root_idx, int val) {
        int new_root = clone_node(root_idx);
        node_pool[new_root].count++;

        int curr_new = new_root;
        int curr_old = root_idx;

        for (int i = BITS - 1; i >= 0; --i) {
            int bit = (val >> i) & 1;
            int old_child_idx = node_pool[curr_old].children[bit];
            int new_child_idx = clone_node(old_child_idx);
            
            node_pool[curr_new].children[bit] = new_child_idx;
            node_pool[new_child_idx].count++;

            curr_new = new_child_idx;
            curr_old = old_child_idx;
        }
        return new_root;
    }

    int query_max_xor(int l_root_idx, int r_root_idx, int x) {
        int y = 0;
        for (int i = BITS - 1; i >= 0; --i) {
            int bit = (x >> i) & 1;
            int required_bit = 1 - bit;

            int r_child_idx = node_pool[r_root_idx].children[required_bit];
            int l_child_idx = node_pool[l_root_idx].children[required_bit];
            
            if (node_pool[r_child_idx].count > node_pool[l_child_idx].count) {
                y |= (required_bit << i);
                r_root_idx = r_child_idx;
                l_root_idx = l_child_idx;
            } else {
                y |= (bit << i);
                r_root_idx = node_pool[r_root_idx].children[bit];
                l_root_idx = node_pool[l_root_idx].children[bit];
            }
        }
        return y;
    }

public:
    PersistentBinaryTrie(int max_nodes) {
        node_pool.resize(max_nodes * (BITS + 2));
        node_idx = 1;
        roots.reserve(max_nodes + 1);
        roots.push_back(0);
    }

    void add(int x) {
        roots.push_back(insert_internal(roots.back(), x));
    }
    
    int get_max_xor(int l, int r, int x) {
        // Note: The PBT works on a 0-indexed array, but the problem uses 1-based ranges.
        // The calling context must handle this conversion.
        return query_max_xor(roots[l - 1], roots[r], x);
    }
};


// --- Solver for the "Klasika" Problem ---

class KlasikaSolver {
private:
    struct Edge {
        int to;
        int weight;
    };

    int node_count;
    std::vector<std::vector<Edge>> adj;
    std::vector<int> dist; // XOR sum from root 1 to node i

    // For mapping tree to 1D array
    std::vector<int> tin, tout, dfs_order;
    int timer;

    void dfs_flattener(int u, int p, int current_xor_dist) {
        tin[u] = ++timer;
        dfs_order[timer] = u;
        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:
    KlasikaSolver(int max_q) {
        node_count = 1;
        adj.resize(max_q + 2);
        dist.resize(max_q + 2);
        tin.resize(max_q + 2);
        tout.resize(max_q + 2);
        dfs_order.resize(max_q + 2);
        dist[1] = 0;
    }

    void add_node(int parent, int weight) {
        node_count++;
        adj[parent].push_back({node_count, weight});
        adj[node_count].push_back({parent, weight}); // Assuming undirected for dist calculation
    }

    int process_query(int a, int b) {
        // 1. Flatten the current tree structure with a DFS
        timer = 0;
        dfs_flattener(1, 0, 0);

        // 2. Build a temporary PBT on the DFS-ordered distances
        PersistentBinaryTrie pbt(node_count);
        for (int i = 1; i <= node_count; ++i) {
            int node_id = dfs_order[i];
            pbt.add(dist[node_id]);
        }

        // 3. The subtree of `b` is now the range [tin[b], tout[b]]
        int l = tin[b];
        int r = tout[b];
        int val_a = dist[a];

        // 4. Query the PBT for the best partner and return the max XOR value
        int best_partner = pbt.get_max_xor(l, r, val_a);
        return val_a ^ best_partner;
    }
};


void solve() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int q;
    std::cin >> q;

    KlasikaSolver solver(q);

    for (int i = 0; i < q; ++i) {
        std::string type;
        std::cin >> type;
        if (type == "Add") {
            int x, y;
            std::cin >> x >> y;
            solver.add_node(x, y);
        } else { // Query
            int a, b;
            std::cin >> a >> b;
            std::cout << solver.process_query(a, b) << nl;
        }
    }
}

int main() {
    solve();
    return 0;
}

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