Submission #492805

#	Time	Username	Problem	Language	Result	Execution time	Memory
492805		paulomiranda98	Klasika (COCI20_klasika)	C++17	33 / 110	1076 ms	524292 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=29; 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=29; 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;
  }
};
 
 
class SegTreeIterative{
private:
  vector<XorTrie> st;
  int n;
public:
  SegTreeIterative(int sz){
    for (n = 1; n < sz; n <<= 1);
    st.resize(n << 1);
  }
  //0-indexed
  void add(int i, int x){
    st[i += n].add(x);
    for (i >>= 1; i; i >>= 1)
      st[i].add(x);
  }
  //0-indexed [l, r]
  int query(int l, int r, int x){
    int ans = 0;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1){
      if (l & 1)
        ans = max(ans, st[l++].max(x));
      if (r & 1)
        ans = max(st[--r].max(x), ans);
    }
    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);
  SegTreeIterative st(last);
  st.add(in[1], v[1]);
  
  for(auto [op, a, b]: queries){
    if(op == "Add"){
      st.add(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: 0 / 33
• Subtask 4: 0 / 44