Submission #624720

#	Time	Username	Problem	Language	Result	Execution time	Memory
624720		MilosMilutinovic	Klasika (COCI20_klasika)	C++14	110 / 110	2240 ms	443944 KiB

klasika

/**
 *    author:  wxhtzdy
 *    created: 08.08.2022 17:17:05
**/
#include <bits/stdc++.h>

using namespace std;

struct node {
  set<int> ids;
  node *ch[2];
  node() {
    ch[0] = NULL;
    ch[1] = NULL;
  }
};

node root = node();

void Add(node *nd, int i, int v, int id) {
  if (i < 0) {
    return;
  }
  int bit = (v >> i & 1);
  if (nd->ch[bit] == NULL) {
    nd->ch[bit] = new node();
  }
  nd->ch[bit]->ids.insert(id);
  Add(nd->ch[bit], i - 1, v, id);
}

int ans = 0;

void Go(node *nd, int i, int v, int L, int R) {
  if (i < 0) {
    return;  
  }
  int bit = (v >> i & 1);
  if (nd->ch[bit ^ 1] != NULL && nd->ch[bit ^ 1]->ids.lower_bound(L) != nd->ch[bit ^ 1]->ids.lower_bound(R + 1)) {
    ans += (1 << i);
    Go(nd->ch[bit ^ 1], i - 1, v, L, R);
  } else {
    Go(nd->ch[bit], i - 1, v, L, R);
  }
}
  

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int q;
  cin >> q;
  vector<string> op(q);
  vector<int> x(q);
  vector<int> y(q);
  int n = 1;
  vector<vector<pair<int, int>>> g(1);
  for (int i = 0; i < q; i++) {
    cin >> op[i] >> x[i] >> y[i];
    if (op[i] == "Add") {
      --x[i];
      g.push_back({});
      g[x[i]].emplace_back(n, y[i]);  
      n += 1;
    } else {
      --x[i]; --y[i];
    }
  }
  vector<int> dep(n);
  vector<int> tin(n);
  vector<int> tout(n);
  int T = -1;
  function<void(int, int)> Dfs = [&](int v, int pr) {
    tin[v] = ++T;
    for (auto& p : g[v]) {
      int u = p.first;
      int w = p.second;
      if (u != pr) {
        dep[u] = dep[v] ^ w;
        Dfs(u, v);
      }
    }
    tout[v] = T;
  };
  Dfs(0, 0);
  int idx = 1;
  Add(&root, 30, dep[0], tin[0]);
  for (int i = 0; i < q; i++) {
    if (op[i] == "Add") {
      Add(&root, 30, dep[idx], tin[idx]);
      idx += 1;  
    } else {                            
      ans = 0;
      Go(&root, 30, dep[x[i]], tin[y[i]], tout[y[i]]);
      cout << ans << '\n';
    }  
  }                         
  return 0;
}

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