oj.uz

Submission #492798

# Submission time Handle Problem Language Result Execution time Memory
492798 2021-12-09T01:43:13 Z paulomiranda98 Klasika (COCI20_klasika) C++14
0 / 110
 640 ms 343240 KB 
#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];
  int leaf;
  int count;
  Vertex() {
    fill(begin(next), end(next), -1);
    leaf = 0;
    count = 0;
  }
};
struct XorTrie{
  vector<Vertex> trie;
  XorTrie(){
    trie.emplace_back();
  }
  void add(int x) {
    int v = 0;
    trie[v].count++;
    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];
      trie[v].count++;
    }
    trie[v].leaf++;
  }
  int max(int x) {
    int v = 0;
    int 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];
int v[MAXN], T;

void build(int u, int x){
  in[u] = T++;

  for(int to: adj[u])
    build(to, x ^ v[u]);

  v[u] ^= x;

  out[u] = T-1;
}

int xorPath(int a, int b){
  return v[a] ^ v[b];
}

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"){
      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(q);
  
  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

klasika.cpp: In function 'int main()':
klasika.cpp:139:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  139 |   for(auto [op, a, b]: queries){
      |            ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Incorrect 4 ms 5344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Incorrect 4 ms 5344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 640 ms 343240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Incorrect 4 ms 5344 KB Output isn't correct
3 Halted 0 ms 0 KB -