Submission #1306440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306440		Born_To_Laugh	Klasika (COCI20_klasika)	C++17	33 / 110	732 ms	589824 KiB

klasika

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
// #define int ll
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;
struct trie
{
    struct node {
        int exist = 0;
        array<int, 2> child;
        node(){
            child.fill(-1);
        }
    };
    int id = 0;
    vector<node> tree;
    trie(){
        tree.emplace_back();
    }
    int new_node(){
        id++;
        if(id >= tree.size()){
            tree.push_back(node());
        }
        return id;
    }
    void add(int a){
        int pos = 0;
        for(int i=30; i>=0; --i){
            int val = (a >> i) & 1;
            if(tree[pos].child[val] == -1){
                tree[pos].child[val] = new_node();
            }
            pos = tree[pos].child[val];
        }
        tree[pos].exist++;
    }
    int walk(int a){
        int pos = 0;
        int ans = 0;
        for(int i=30; i>=0; --i){
            int val = 1 - ((a >> i) & 1);
            if(tree[pos].child[val] != -1){
                pos = tree[pos].child[val];
                ans |= (val << i);
            }
            else if(tree[pos].child[1 - val] != -1){
                pos = tree[pos].child[1 - val];
                ans |= ((1 - val) << i);
            }
            else break;
        }
        if(tree[pos].exist > 0)return ans;
        else return a;
    }
};
class Segment_Tree
{
private:
    int n;
    vector<trie> tree;
    void PointUpd(int id, int l, int r, int pos, int val){
        tree[id].add(val);
        if(l == r)return;
        int mid = (l + r) >> 1;
        if(pos <= mid)PointUpd(id << 1, l, mid, pos, val);
        else PointUpd(id << 1|1, mid + 1, r, pos, val);
    }
    int qr(int id, int l, int r, int lo, int hi, int val){
        if(l > hi || r < lo)return val;
        else if(l >= lo && r <= hi){
            return tree[id].walk(val);
        }
        int mid = (l + r) >> 1;
        int val1 = qr(id << 1, l, mid, lo, hi, val);
        int val2 = qr(id << 1|1, mid + 1, r, lo, hi, val);
        if((val1 ^ val) > (val2 ^ val))return val1;
        else return val2;
    }
public:
    void init(int len){
        n = len + 1;
        tree.assign(n << 2, trie());
    }
    void PointUpd(int pos, int val){
        PointUpd(1, 1, n, pos, val);
    }
    int qr(int lo, int hi, int val){
        return qr(1, 1, n, lo, hi, val);
    }
};

const int maxn = 2e5 + 10;
int n = 1, q;
int xorr[maxn];//xor 1 -> a = xorr[a]

vector<vector<int>> qr;
vector<int> adj[maxn];
int tin[maxn], tout[maxn];
int eul = 0;
Segment_Tree st;


void dfs(int a){
    tin[a] = ++eul;
    for(auto &elm: adj[a]){
        dfs(elm);
    }
    tout[a] = eul;
}
void ope1(vector<int> cc){
    int a = cc[1], n = cc[2], b = cc[3];
    xorr[n] = xorr[a] ^ b;
    st.PointUpd(tin[n], xorr[n]);
}
int ope2(vector<int> cc){
    int a = cc[1], b = cc[2];
    return xorr[a] ^ st.qr(tin[b], tout[b], xorr[a]);
}
void solve(){
    cin >> q;
    for(int i=1; i<=q; ++i){
        string x;cin >> x;
        int a, b;cin >> a >> b;
        if(x[0] == 'A'){
            adj[a].push_back(++n);
            qr.push_back({1, a, n, b});
        }
        else qr.push_back({2, a, b});
    }
    st.init(n);
    dfs(1);
    st.PointUpd(tin[1], 0);
    for(auto &elm: qr){
        if(elm[0] == 1){
            ope1(elm);
        }
        else cout << ope2(elm) << '\n';
    }
}
signed main(){
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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