제출 #1228217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228217		mnnit_prakharg	Klasika (COCI20_klasika)	C++20	0 / 110	28 ms	8512 KiB

klasika

#pragma GCC optimize("O3","inline")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

static const int MAXL = 33;  // we’ll store bits 32..0

struct Node {
    Node* a[2] = {nullptr,nullptr};
    set<int> times;
};

struct Trie {
    Node* head;
    Trie() { head = new Node(); }
};

struct Query {
    bool isAdd;
    int x;    // for Add: parent‑index, for Query: node a
    int y;    // for Add: weight  , for Query: node b
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int Q;
    cin >> Q;
    vector<Query> qs(Q);
    int totalNodes = 1;

    // 1) read queries and count how many nodes we'll have
    for(int i = 0; i < Q; i++){
        string ty;
        int x; ll w;
        cin >> ty >> x >> w;
        if (ty == "Add") {
            qs[i] = { true, x-1, (int)w };
            totalNodes++;
        } else {
            // Query a b
            qs[i] = { false, x-1, (int)(w-1) };
        }
    }

    // 2) build the static tree, do one DFS to get xra[], tin[], tout[]
    vector<vector<pair<int,ll>>> adj(totalNodes);
    int nextId = 1;
    for(auto &q : qs){
        if (q.isAdd) {
            adj[q.x].emplace_back(nextId++, q.y);
        }
    }

    vector<ll> xra(totalNodes, 0);
    vector<int> tin(totalNodes), tout(totalNodes);
    int timer = 0;
    function<void(int)> dfs = [&](int u){
        tin[u] = timer++;
        for(auto &e : adj[u]){
            int v = e.first;
            ll w  = e.second;
            xra[v] = xra[u] ^ w;
            dfs(v);
        }
        tout[u] = timer++;
    };
    dfs(0);

    // 3) second pass: interleave trie‑inserts on Add and greedy XOR‑queries
    Trie trie;
    vector<ll> answers;
    nextId = 1;  // for Add ordering

    for(auto &q : qs){
        if (q.isAdd) {
            int u = nextId++;
            ll val = xra[u];
            Node* cur = trie.head;
            for(int b = MAXL-1; b >= 0; --b){
                int bit = (val >> b) & 1;
                if (!cur->a[bit]) 
                    cur->a[bit] = new Node();
                cur = cur->a[bit];
                cur->times.insert(tin[u]);
            }
        } else {
            int a = q.x, b = q.y;
            ll X = xra[a];
            int L = tin[b], R = tout[b];

            ll ans = 0;
            Node* cur = trie.head;
            for(int bbit = MAXL-1; bbit >= 0; --bbit){
                int want = 1 - ((X >> bbit) & 1);
                Node* cand = cur->a[want];
                bool ok = false;
                if (cand) {
                    auto it = cand->times.lower_bound(L);
                    if (it != cand->times.end() && *it <= R)
                        ok = true;
                }
                if (ok) {
                    ans |= (1LL << bbit);
                    cur = cand;
                } else {
                    cur = cur->a[1-want];
                }
            }
            answers.push_back(ans);
        }
    }

    // 4) output answers
    for (ll v : answers) 
        cout << v << " ";
    cout << "\n";
    return 0;
}

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