제출 #1247501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247501		dfhdfhdsf	Klasika (COCI20_klasika)	C++20	33 / 110	687 ms	589824 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
const int MAXQ = 200000;
struct Query { int type, x, y; };
int Q;
vector<Query> ops;
vector<vector<int>> children;
vector<uint> val;
vector<int> tin, tout;
int timer = 0;

// Trie for XOR
struct Trie {
    Trie* ch[2];
    Trie() { ch[0]=ch[1]=nullptr; }
};

void trie_insert(Trie* &root, uint x) {
    if (!root) root = new Trie();
    Trie* p = root;
    for (int i = 30; i >= 0; --i) {
        int b = (x >> i) & 1;
        if (!p->ch[b]) p->ch[b] = new Trie();
        p = p->ch[b];
    }
}

uint trie_query(Trie* root, uint x) {
    if (!root) return 0;
    Trie* p = root;
    uint res = 0;
    for (int i = 30; i >= 0; --i) {
        int b = (x >> i) & 1;
        if (p->ch[b^1]) {
            res |= (1u << i);
            p = p->ch[b^1];
        } else {
            p = p->ch[b];
        }
    }
    return res;
}

// Segment tree of tries
vector<Trie*> seg;

void seg_update(int idx, int l, int r, int pos, uint x) {
    trie_insert(seg[idx], x);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) seg_update(idx<<1, l, mid, pos, x);
    else seg_update(idx<<1|1, mid+1, r, pos, x);
}

uint seg_query(int idx, int l, int r, int ql, int qr, uint x) {
    if (qr < l || r < ql || !seg[idx]) return 0;
    if (ql <= l && r <= qr) {
        return trie_query(seg[idx], x);
    }
    int mid = (l + r) >> 1;
    return max(seg_query(idx<<1, l, mid, ql, qr, x),
               seg_query(idx<<1|1, mid+1, r, ql, qr, x));
}

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

    cin >> Q;
    ops.resize(Q);
    children.assign(Q+2, {});
    val.assign(Q+2, 0);
    for (int i = 0; i < Q; ++i) {
        string cmd;
        cin >> cmd;
        if (cmd == "Add") {
            ops[i].type = 1;
            cin >> ops[i].x >> ops[i].y;
            // record
        } else {
            ops[i].type = 2;
            cin >> ops[i].x >> ops[i].y;
        }
    }
    
    // build tree structure and val
    int nodes = 1;
    for (int i = 0; i < Q; ++i) {
        if (ops[i].type == 1) {
            int x = ops[i].x;
            int y = ops[i].y;
            ++nodes;
            children[x].push_back(nodes);
            val[nodes] = val[x] ^ (uint)y;
        }
    }
    
    // euler tour iterative
    tin.assign(nodes+1, 0);
    tout.assign(nodes+1, 0);
    vector<pair<int,int>> st;
    st.reserve(nodes*2);
    st.emplace_back(1, 0);
    while (!st.empty()) {
        auto &pr = st.back();
        int u = pr.first, &idx = pr.second;
        if (idx == 0) {
            tin[u] = ++timer;
        }
        if (idx < (int)children[u].size()) {
            int v = children[u][idx++];
            st.emplace_back(v, 0);
        } else {
            tout[u] = timer;
            st.pop_back();
        }
    }
    
    // seg tree init
    seg.assign(4*(nodes+2), nullptr);
    // insert root
    seg_update(1, 1, nodes, tin[1], val[1]);
    
    // process queries
    nodes = 1;
    for (int i = 0; i < Q; ++i) {
        if (ops[i].type == 1) {
            int x = ops[i].x;
            ++nodes;
            seg_update(1, 1, timer, tin[nodes], val[nodes]);
        } else {
            int a = ops[i].x, b = ops[i].y;
            uint ans = seg_query(1, 1, timer, tin[b], tout[b], val[a]);
            cout << ans << '\n';
        }
    }
    return 0;
}

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