Submission #492804

#	Time	Username	Problem	Language	Result	Execution time	Memory
492804		paulomiranda98	Klasika (COCI20_klasika)	C++17	33 / 110	1102 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=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;
  }
};


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];
bool active[MAXN];
int v[MAXN], T;
/*
void build(int u){
  in[u] = T++;

  for(int to: adj[u]){
    v[to] ^= v[u];
    build(to);
  }

  out[u] = T-1;
}*/

void build(){
  stack<pii> st;
  st.emplace(1, -1);
  while(!st.empty()){
    auto [u, i] = st.top();
    st.pop();
    if(i == -1){
      in[u] = T++;
      st.emplace(u, 0);
    }else if(i < adj[u].size()){
      st.emplace(u, i+1);
      int to = adj[u][i];
      v[to] ^= v[u];
      st.emplace(adj[u][i], -1);
    }else{
      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();
  SegTreeIterative st(q);
  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;
}

Compilation message (stderr)

klasika.cpp: In function 'void build()':
klasika.cpp:112:16: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     }else if(i < adj[u].size()){
      |              ~~^~~~~~~~~~~~~~~

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