Submission #1090921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090921		fryingduc	Klasika (COCI20_klasika)	C++17	110 / 110	2292 ms	476716 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 = 30;
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 {
    struct node {
        set<int> all;
        int nt[2];
        node(){
            nt[0] = nt[1] = 0;
        }
    };
    vector<node> t;
    int cc;
    trie() {
        t.push_back({});
        t.push_back({});
        cc = 1;
    }
    vector<int> :: iterator it;
    void add(int p, int x){
        int v = 1;
        for (int i = lg; i >= 0; i--){
            bool bit = (x >> i) & 1;
            if (!t[v].nt[bit]){
                t[v].nt[bit] = ++cc;
                t.push_back({});
            }
            v = t[v].nt[bit];
            t[v].all.insert(p);
        }
    }
    int get(int l, int r, int x){
        int out = 0, v = 1;
        for (int i = lg; i >= 0; i--){
            bool bit = (x >> i) & 1;
            int k = t[v].nt[!bit];
            auto it = t[k].all.lower_bound(l);
            if (it != t[k].all.end() && (*it) <= r){
                v = k;
                out += (1 << i);
                continue;
            }
            v = t[v].nt[bit];
        }
        return out;
    }
} t;
 
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);
  t.add(1, 0);
  
  for(int i = 1; i <= q; ++i) {
    if(!op[i]) {
      t.add(tin[qx[i]], dep[qx[i]]);
    }
    else {
      int u = qx[i], v = qy[i];
      cout << t.get(tin[v], tout[v], dep[u]) << '\n';
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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