Submission #624688

#	Time	Username	Problem	Language	Result	Execution time	Memory
624688		MilosMilutinovic	Klasika (COCI20_klasika)	C++14	33 / 110	2361 ms	524288 KiB

klasika

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

using namespace std;

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;
  vector<set<int>> ids(1);
  vector<vector<int>> trie(1, vector<int>(2, -1));
  auto Add = [&](int v, int id) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
      int bit = (v >> i & 1);
      if (trie[p][bit] == -1) {
        trie[p][bit] = (int) trie.size();
        trie.push_back(vector<int>(2, -1));
        ids.push_back({});
      }    
      p = trie[p][bit];
      ids[p].insert(id);     
    }
  };
  Add(dep[0], tin[0]);
  for (int i = 0; i < q; i++) {
    if (op[i] == "Add") {
      Add(dep[idx], tin[idx]);
      idx += 1;  
    } else {
      int p = 0;
      int ans = 0;
      for (int j = 30; j >= 0; j--) {
        int bit = (dep[x[i]] >> j & 1);
        if (trie[p][bit ^ 1] != -1) {
          auto it = ids[trie[p][bit ^ 1]].lower_bound(tin[y[i]]);
          if (it != ids[trie[p][bit ^ 1]].end() && *it <= tout[y[i]]) {
            ans += (1 << j);
            p = trie[p][bit ^ 1];
          } else {
            p = trie[p][bit];
          }
        } else {
          p = trie[p][bit];
        }
      }
      cout << ans << '\n';
    }  
  }                         
  return 0;
}

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