oj.uz

Submission #889561

# Submission time Handle Problem Language Result Execution time Memory
889561 2023-12-20T02:31:44 Z dimashhh Klasika (COCI20_klasika) C++17
0 / 110
 452 ms 127864 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 1, MOD = 998244353,b = 30;
typedef long long ll;

vector<array<int,3>> qr;
int q,tin[N],tout[N],n = 1,d[N],timer = 0;
vector<pair<int,int>> g[N];
void dfs(int v){
    tin[v] = ++timer;
    // cout << v << ' ' << d[v] << '\n';
    for(auto [to,w]:g[v]){
        d[to] = (d[v] ^ w);
        dfs(to);
    }
    tout[v] = ++timer;
    // cout << v << ' ' << tin[v] << ' ' << tout[v] << '\n';
}
struct node{
    node *next[2];
    set<int> st;
    node(){
        for(int i = 0;i < 2;i++){
            next[i] = nullptr;
        }
    }
};
node *root = new node();
void add(int tadd,int val){
    node *cur = root;
    for(int i = b;i >= 0;i--){
        int nv = ((val >> i) & 1);
        
        if(!cur->next[nv])
            cur->next[nv] = new node();
        cur = cur->next[nv];
        cur->st.insert(tadd);
    }
}
int get(int val,int l,int r){
    node *cur = root;
    int ret = 0;
    for(int i = b;i >= 0;i--){
        int nd = (val >> i) & 1;
        nd ^= 1;
        bool ok = false;
        if(cur->next[nd]){
            auto it = cur->next[nd]->st.lower_bound(l);
            if(it != cur->next[nd]->st.end() && *it <= r){
                ok = 1;
            }
        }
        if(ok){
            ret += (1ll << i);
            cur = cur->next[nd];
        }else if(cur->next[!nd]){
            cur = cur->next[!nd];
        }else break;
    }
    return ret;
}
void test(){
    cin >> q;
    for(int i = 1;i <= q;i++){
        string tp;
        cin >> tp;
        if(tp[0] == 'A'){
            ++n;
            int x,y;
            cin >> x >> y;
            g[x].push_back({n,y});
            qr.push_back({1,n,y});
            // cout << x << ' ' << n << '\n';
        }else{
            int x,y;
            cin >> x >> y;
            qr.push_back({2,x,y});
        }
    }
    dfs(1);
    for(auto i:qr){
        if(i[0] == 1){
            add(tin[i[1]],d[i[1]]);
            // cout << tin[i[1]] << ' ' << d[i[1]] << "x\n";
        }else{
            // cout << d[i[1]] << ' ' << tin[i[2]] << ' ' << tout[i[2]] << '\n';
            cout << get(d[i[1]],tin[i[2]],tout[i[2]]) << '\n';
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1; // cin >> T;
    while (T--)
        test();
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Incorrect 2 ms 11100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Incorrect 2 ms 11100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 452 ms 127864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Incorrect 2 ms 11100 KB Output isn't correct
3 Halted 0 ms 0 KB -