제출 #1252759

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

klasika

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

#define nl "\n"

// --- Solver for the "Klasika" Problem (Correct Offline Approach) ---
// This solution is a clean, encapsulated implementation of the accepted algorithm.
// It works by processing queries offline, flattening the final tree with a DFS,
// and using a single Binary Trie where each node contains a std::set of DFS
// 'in' times to answer subtree queries efficiently.

class KlasikaSolver {
private:
    static const int BITS = 30;

    // The Trie structure, where each node holds a set of indices.
    struct Trie {
        struct Node {
            Node* children[2];
            std::set<int> ids;
            Node() : children{nullptr, nullptr} {}
        };

        Node* root;

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

        // Inserts the pre-calculated XOR sum for a given node `u`
        // by adding its `in_time` to the sets along the path.
        void insert(int in_time, int xor_sum) {
            Node* curr = root;
            for (int i = BITS - 1; i >= 0; --i) {
                int bit = (xor_sum >> i) & 1;
                if (!curr->children[bit]) {
                    curr->children[bit] = new Node();
                }
                curr = curr->children[bit];
                curr->ids.insert(in_time);
            }
        }

        // Finds the max XOR of `val` with any node in the subtree of `u`.
        int query_max(int val, int in_u, int out_u) {
            Node* curr = root;
            int best_partner_xor = 0;
            for (int i = BITS - 1; i >= 0; --i) {
                int bit = (val >> i) & 1;
                int required_bit = 1 - bit;

                // Check if a valid partner exists down the desired path.
                if (curr->children[required_bit]) {
                    auto& s = curr->children[required_bit]->ids;
                    auto it = s.lower_bound(in_u);
                    if (it != s.end() && *it <= out_u) {
                        // Found a partner in the subtree range. Take this path.
                        best_partner_xor |= (required_bit << i);
                        curr = curr->children[required_bit];
                        continue;
                    }
                }
                
                // Forced to take the other path.
                best_partner_xor |= (bit << i);
                curr = curr->children[bit];
            }
            return val ^ best_partner_xor;
        }
    };

    struct Query {
        int type; // 1 for Add, 2 for Query
        int u, v;
    };

    std::vector<std::vector<std::pair<int, int>>> adj;
    std::vector<int> dist, tin, tout;
    int timer;
    int node_count;

    // DFS on the final tree to compute distances and in/out times.
    void dfs_flattener(int u, int p, int current_xor_dist) {
        tin[u] = ++timer;
        dist[u] = current_xor_dist;
        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (v != p) {
                dfs_flattener(v, u, current_xor_dist ^ w);
            }
        }
        tout[u] = timer;
    }

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

        int q;
        std::cin >> q;

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

        // 1. Read all queries and build the final adjacency list.
        for (int i = 0; i < q; ++i) {
            std::string type;
            std::cin >> type >> queries[i].u >> queries[i].v;
            if (type == "Add") {
                queries[i].type = 1;
                node_count++;
                adj[queries[i].u].push_back({node_count, queries[i].v});
            } else {
                queries[i].type = 2;
            }
        }

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

        // 3. Process queries chronologically, inserting into the Trie as we go.
        Trie trie;
        int current_nodes_added = 1;
        trie.insert(tin[1], dist[1]);

        for (const auto& query : queries) {
            if (query.type == 1) { // Add
                current_nodes_added++;
                trie.insert(tin[current_nodes_added], dist[current_nodes_added]);
            } else { // Query
                int a = query.u;
                int b = query.v;
                std::cout << trie.query_max(dist[a], tin[b], tout[b]) << nl;
            }
        }
    }
};

int main() {
    KlasikaSolver solver;
    solver.solve();
    return 0;
}

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