Submission #1189741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189741		zNatsumi	Klasika (COCI20_klasika)	C++20	110 / 110	1198 ms	359672 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;
using tp = array<int, 3>;

const int N = 2e5 + 5;

int q, it, pref[N], in[N], out[N];
vector<tp> QUERY;
vector<ii> ad[N];

namespace trie{
  struct node{
    node *child[2];
    vector<int> v, bit;

    node(){
      child[0] = child[1] = NULL;
      v.clear(); bit.clear();
    }

    void update(int x, int y){
      for(int i = lower_bound(v.begin(), v.end(), x) - v.begin() + 1; i <= v.size(); i += i & -i) bit[i - 1] += y;
    }
    int pre(int x){
      int res = 0;
      for(int i = upper_bound(v.begin(), v.end(), x) - v.begin(); i > 0; i -= i & -i) res += bit[i - 1];
      return res;
    }
    int get(int l, int r){ return pre(r) - pre(l - 1); }
  };

  node *root = new node();

  void add(int x, int pos){
    auto p = root;
    for(int i = 30; i >= 0; i--){
      int c = x >> i & 1;
      if(p->child[c] == NULL) p->child[c] = new node();
      p = p->child[c];
      p->v.push_back(pos);
      p->bit.emplace_back();
    }
  }
  void upd(int x, int pos){
    auto p = root;
    for(int i = 30; i >= 0; i--){
      int c = x >> i & 1;
      p = p->child[c];
      p->update(pos, 1);
    }
  }
  int get(int x, int u){
    int res = 0;
    auto p = root;
    for(int i = 30; i >= 0; i--){
      int c = x >> i & 1;

      if(p->child[c ^ 1] && p->child[c ^ 1]->get(in[u], out[u])){
        res |= (1 << i);
        p = p->child[c ^ 1];
      }else
        p = p->child[c];
    }
    return res;
  }
};

void dfs0(int u, int p){
  in[u] = ++it;
  trie::add(pref[u], in[u]);

  for(auto [v, w] : ad[u]){
    pref[v] = pref[u] ^ w;
    dfs0(v, u);
  }
  out[u] = it;
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> q;
  it = 1;
  for(int i = 1; i <= q; i++){
    string s; int a, b;
    cin >> s >> a >> b;

    if(s == "Add"){
      ad[a].push_back({++it, b});
      QUERY.push_back({0, a, b});
    }else{
      QUERY.push_back({1, a, b});
    }
  }

  it = 0;
  dfs0(1, -1);

  it = 1;
  trie::upd(pref[it], in[it]);
  for(auto [ty, a, b] : QUERY){
    if(!ty){
      ++it;
      trie::upd(pref[it], in[it]);
    }else{
      cout << trie::get(pref[a], b) << "\n";
    }
  }

  return 0;
}

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