Submission #492813

#	Time	Username	Problem	Language	Result	Execution time	Memory
492813		paulomiranda98	Klasika (COCI20_klasika)	C++17	110 / 110	3712 ms	55728 KiB

klasika

#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define endl '\n'
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1000000007;
const int dx[] = { 0, 0, -1, 1, 1, -1,  1, -1};
const int dy[] = {-1, 1,  0, 0, 1, -1, -1,  1};
 
struct Vertex {
  int next[2];
  Vertex() {
    next[0] = next[1] = -1;
  }
};
struct XorTrie{
  vector<Vertex> trie;
  XorTrie(){
    trie.emplace_back();
  }
  void add(int x) {
    int v = 0;
    for(int i=30; i>=0; i--){
      int c = (x>>i)&1;
      if (trie[v].next[c] == -1) {
        trie[v].next[c] = trie.size();
        trie.emplace_back();
      }
      v = trie[v].next[c];
    }
  }
  int max(int x) {
    int v = 0, ans = 0;
    for(int i=30; i>=0; i--){
      int c = (x>>i)&1;
      if(trie[v].next[!c] != -1){
        ans |= (1<<i);
        v = trie[v].next[!c];
      }else if(trie[v].next[c] != -1){
        v = trie[v].next[c];
      }else{
        return 0;
      }
    }
    return ans;
  }
};
 

struct SqrtDecomposition{
  const int sqrtLen = 1000;
  vector<XorTrie> block;
  vector<int> v;
  SqrtDecomposition(int sz){
    int n = sz;
    v.resize(n, -1);
    block.resize(sqrtLen + 5);
  }
  //0-indexed
  void update(int idx, int new_value){
    v[idx] = new_value;
    block[idx / sqrtLen].add(new_value);
  }
  //0-indexed [l, r]
  int query(int l, int r, int x){
    int ans = 0;
    int c_l = l / sqrtLen, c_r = r / sqrtLen;
    if (c_l == c_r){
      for (int i = l; i <= r; i++){
        if(v[i] != -1)
          ans = max(ans, x^v[i]);
      }
    }else{
      for (int i = l, end = (c_l + 1) * sqrtLen - 1; i <= end; i++){
        if(v[i] != -1)
          ans = max(ans, x ^ v[i]);
      }
      for (int i = c_l + 1; i <= c_r - 1; i++)
        ans = max(ans, block[i].max(x));
      for (int i = c_r * sqrtLen; i <= r; i++){
        if(v[i] != -1)
          ans = max(ans, x^v[i]);
      }
    }
    return ans;
  }
};

const int MAXN = 200010;
 
vector<int> adj[MAXN];
int in[MAXN], out[MAXN];
int v[MAXN], T;
 
void build(int u, int x){
  in[u] = T++;
 
  v[u] = x;
 
  for(int to: adj[u])
    build(to, x ^ v[to]);
 
  out[u] = T-1;
}
 
int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  int q;
  cin >> q;
  
  vector<tuple<string, int, int>> queries;
  
  int last = 1;
  
  for(int i=0; i<q; i++){
    string op;
    int a, b;
    cin >> op >> a >> b;
    if(op == "Add"){
      last++;
      adj[a].push_back(last);
      v[last] = b;
      queries.emplace_back(op, last, -1);
    }else{
      queries.emplace_back(op, a, b);
    }
  }
  
  build(1, 0);
  SqrtDecomposition st(last);
  st.update(in[1], v[1]);
  
  for(auto [op, a, b]: queries){
    if(op == "Add"){
      st.update(in[a], v[a]);
    }else{
      cout << st.query(in[b], out[b], v[a]) << endl;
    }
  }
  
  return 0;
}

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