제출 #1307532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307532		Born_To_Laugh	Klasika (COCI20_klasika)	C++17	0 / 110	435 ms	124948 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;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;
struct trie
{
    struct node{
        array<int, 2> child;
        set<int> tin;
        node(){
            child.fill(-1);
        }
    };
    int cnt = 0;
    vector<node> tree;
    bool check(int id, int l, int r){
        if(id == -1)return 0;
        auto it = tree[id].tin.lower_bound(l);
        if(it == tree[id].tin.end())return 0;
        return (*it) <= r;
    }
    trie(){
        tree.emplace_back();
    }
    int new_node(){
        ++cnt;
        if(cnt >= tree.size())tree.emplace_back();
        return cnt;
    }
    void add(int a, int tin){
        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].tin.insert(tin);
        }
    }
    int qr(int a, int l, int r){
        int ans = 0;
        int pos = 0;
        for(int i=30; i>=0; --i){
            int val = 1 - ((a >> i) & 1);
            if(check(tree[pos].child[val], l, r)){
                pos = tree[pos].child[val];
                ans |= (val << i);
            }
            else if(check(tree[pos].child[1 - val], l, r)){
                pos = tree[pos].child[1 - val];
                ans |= ((1 - val) << i);
            }
            else return a;
        }
        return ans;
    }
};

const int maxn = 2e5 + 10;

int cnt = 1, q, eul = 0;
int tin[maxn], tout[maxn], xorr[maxn];
vector<int> adj[maxn];

vector<vector<int>> qr;
trie st;

void dfs(int a){
    tin[a] = ++eul;
    for(auto &elm: adj[a]) dfs(elm);
    tout[a] = eul;
}
void ope1(int a, int n, int b){
    xorr[n] = xorr[a] ^ b;
    st.add(xorr[n], tin[n]);
}
int ope2(int a, int b){
    return xorr[a] ^ st.qr(xorr[a], tin[b], tout[b]);
}

void solve(){
    cin >> q;
    st.add(0, tin[1]);
    for(int i=1; i<=q; ++i){
        string x;cin >> x;
        int a, b;cin >> a >> b;
        if(x[0] == 'A'){
            qr.push_back({1, a, ++cnt, b});
            adj[a].push_back(cnt);
        }
        else qr.push_back({2, a, b});
    }
    dfs(1);
    for(int i=0; i<q; ++i){
        if(qr[i][0] == 1) ope1(qr[i][1], qr[i][2], qr[i][3]);
        else if(qr[i][0] == 2)cout << ope2(qr[i][1], qr[i][2]) << '\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: 0 / 11
• Subtask 2: 0 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44