Submission #1090909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090909		fryingduc	Klasika (COCI20_klasika)	C++17	0 / 110	682 ms	500368 KiB

klasika

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
const int lg = 19;
int q;
int n;
int tin[maxn], tout[maxn], timer;
int op[maxn], qx[maxn], qy[maxn];
int par[maxn];
vector<pair<int, int>> g[maxn];
int dep[maxn], h[maxn];

void pre_dfs(int u) {
  tin[u] = ++timer;
  for(auto e:g[u]) {
    int v = e.first, w = e.second;
    dep[v] = dep[u] ^ w;
    h[v] = h[u] + 1;
    pre_dfs(v);
  }
  tout[u] = timer;
}
struct trie {
  const static int lg = 30;
  struct node {
    node *child[2];
    int cnt;
    node() {
      child[0] = child[1] = nullptr;
      cnt = 0;
    }
  } *root;
  trie() {
    root = new node();
  }
  void add(int x) {
    node *p = root;
    for(int i = lg; i >= 0; --i) {
      int c = (x >> i & 1);
      if(p->child[c] == nullptr) {
        p->child[c] = new node();
      }
      p = p->child[c];
      p->cnt++;
    }
  }
  int get(int x) {
    node *p = root;
    int ans = 0;
    for(int i = lg; i >= 0; --i) {
      int c = (x >> i & 1);
      if(p->child[c ^ 1] and p->child[c ^ 1]->cnt) {
        ans |= (1 << i);
        p = p->child[c ^ 1];
      }
      else {
        if(p->child[c] == nullptr) {
          return ans;
        }
        p = p->child[c];
      }
    }
    return ans;
  }
};
struct segment_tree {
  int n;
  vector<trie> tree;
  segment_tree() {}
  segment_tree(int n) : n(n), tree(n * 4 + 6) {}
  void update(int ind, int l, int r, int pos, int val) {
    tree[ind].add(val);
    if(l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) {
      update(ind << 1, l, mid, pos, val);
    }
    else {
      update(ind << 1 | 1, mid + 1, r, pos, val);
    }
  }
  int get(int ind, int l, int r, int x, int y, int val) {
    if(l > y || r < x) return 0;
    if(x <= l and r <= y) {
      return tree[ind].get(val);
    }
    int mid = (l + r) >> 1;
    return max(get(ind << 1, l, mid, x, y, val), get(ind << 1 | 1, mid + 1, r, x, y, val));
  }
  void update(int pos, int val) {
    update(1, 1, n, pos, val);
  }
  int get(int x, int y , int val) {
    return get(1, 1, n, x, y, val);
  }
} st;
void solve() {
  cin >> q;
  string s;
  n = 1;
  for(int i = 1; i <= q; ++i) {
    cin >> s >> qx[i] >> qy[i];
    if(s[0] == 'Q') {
      op[i] = 1;
    }
    
    if(!op[i]) {
      ++n;
      par[n] = qx[i];
      g[qx[i]].push_back({n, qy[i]});
      qx[i] = n;
    }
  }
  pre_dfs(1);
  st = segment_tree(n);
  
  for(int i = 1; i <= q; ++i) {
    if(!op[i]) {
      st.update(tin[qx[i]], dep[qx[i]]);
    }
    else {
      int u = qx[i], v = qy[i];
      cout << st.get(tin[v], tout[v], dep[u]) << '\n';
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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