Submission #1162192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162192		luishgh	Klasika (COCI20_klasika)	C++20	110 / 110	1784 ms	487180 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

const int MAX = 2e5 + 10;
const int LOG = 32;

vector<int> g[MAX];
int tin[MAX];
int tout[MAX];
int dist[MAX];

int t = 0;

void dfs(int s) {
  tin[s] = ++t;
  for (auto w : g[s]) {
    if (tin[w] != -1) continue;
    dfs(w);
  }
  tout[s] = t;
}

namespace trie {
  int to[MAX*20][2];
  set<int> tt[MAX*20];
  int cnt = 0;

  // x is dist(root, u), v u is the vertex
  void add(int x, int u) {
    int v = 0;
    for (int i = LOG -1; i >= 0; i--) {
      int j = (x >> i) % 2;
      if (to[v][j] != -1) {
        v = to[v][j];
      } else {
        v = to[v][j] = ++cnt;
      }
      tt[v].insert(tin[u]);
    }
  }

  int query(int a, int b) {
    int v = 0;
    a = dist[a];
    int ans = 0;

    for (int i = LOG - 1; i >= 0; i--) {
      int j = (a >> i) % 2;
      ans <<= 1;
      // cerr << v << ' ' << j << ' ';
      int u = to[v][j^1];
      // cerr << u << endl;
      if (u == -1) {
        v = to[v][j];
        continue;
      } else {
        auto it = tt[u].lower_bound(tin[b]);
        // cerr << "Looking for " << tin[b] << " in: ";
        // for (auto iii : tt[u])
        //   cerr << iii << ' ';
        // cerr << endl;
        if(it == tt[u].end() or *it > tout[b]) {
          v = to[v][j];
          continue;
        } else {
          v = u;
          ans++;
        }
      }
    }
    return ans;
  }

}

int main() {_;
  memset(tin, -1, sizeof tin);
  memset(trie::to, -1, sizeof trie::to);
  dist[0] = 0;

  int q; cin >> q;

  int cnt = 0;

  vector<tuple<string, int, int>> queries;

  while (q--) {
    string op; cin >> op;
    int x, y; cin >> x >> y;
    queries.emplace_back(op, x, y);
    if (op != "Add") continue;
    x--;
    g[x].push_back(++cnt);
    dist[cnt] = dist[x] ^ y;
  }

  dfs(0);
  cnt = 0;
  trie::add(dist[cnt], cnt);

  for (auto [s, x, y] : queries) {
    if (s == "Add") {
      cnt++;
      trie::add(dist[cnt], cnt);
    } else {
      x--, y--;
      cout << trie::query(x, y) << endl;
    }
  }

  return 0;
}

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