Submission #844524

#	Time	Username	Problem	Language	Result	Execution time	Memory
844524		vjudge1	Klasika (COCI20_klasika)	C++17	0 / 110	51 ms	14032 KiB

klasika

// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int Q;
  cin >> Q;
  vector<vector<int>> g(1);
  vector<int> V(1, 0);
  vector<array<int, 2>> E(Q);
  for (int i = 0; i < Q; ++i) {
    string T;
    int X, Y;
    cin >> T >> X >> Y;
    if (T == "Add") {
      --X;
      int v = int(g.size());
      V.push_back(V[X] ^ Y);
      g.emplace_back(); 
      g[X].push_back(v);
      E[i] = {-1, v};
    } else {
      --X, --Y;
      E[i] = {X, Y};     
    }
  }
  int N = int(g.size());
  vector<int> tin(N), tout(N);
  int t = 0;
  function<void(int)> Dfs = [&](int v) {
    tin[v] = t++;
    for (auto u : g[v]) {
      Dfs(u);
    }
    tout[v] = t - 1;
  };
  Dfs(0);
  debug(tin, tout, E, V);
  struct node {
    set<int> ids;
    array<node*, 2> to = {NULL, NULL};
  };
  auto Exists = [&](node* v, int l, int r) {
    return (v != NULL && (v->ids.lower_bound(l) != v->ids.lower_bound(r + 1)));
  };
  const int BIT = 30;
  node* trie = new node();
  for (int i = 0; i < Q; ++i) {
    if (E[i][0] == -1) {
      int id = tin[E[i][1]];
      int add = V[E[i][1]];     
      node* cur = trie;
      for (int b = BIT - 1; b >= 0; --b) {
        int go = (add >> b) % 2;
        if (cur->to[go] == NULL) {
          cur->to[go] = new node(); 
        }
        cur = cur->to[go];
        cur->ids.insert(id);
      }              
    } else {
      node* cur = trie;
      auto[A, B] = E[i];
      int other = 0;
      for (int b = BIT - 1; b >= 0; --b) {
        int go = 1 ^ ((V[A] >> b) % 2);
        if (!Exists(cur->to[go], tin[B], tout[B])) {
          go ^= 1;  
        }  
        cur = cur->to[go];
        other |= go << b;
      }
      cout << (other ^ V[A]) << '\n';
    }
  }
}

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