Submission #1123001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123001		duckindog	Klasika (COCI20_klasika)	C++17	110 / 110	1065 ms	108316 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int q;

const int MAXBIT = 30;
struct Trie { 
  struct Node { 
    Node* nxt[2];
    int time;
    Node() : time(N) { 
      nxt[0] = nxt[1] = NULL;
    }
  };

  Node* root;
  Trie() : root(new Node()) {}

  void add(int value, int time) { 
    auto g = root;
    for (int i = MAXBIT; i >= 0; --i) { 
      int bit = (value >> i & 1);
      if (!g->nxt[bit]) g->nxt[bit] = new Node();
      g = g->nxt[bit];
      g->time = min(g->time, time);
    }
  }

  void merge(Node* g1, Node* g2, int ithBit = 30) { 
    g1->time = min(g1->time, g2->time);
    if (ithBit >= 0) { 
      for (int bit = 0; bit <= 1; ++bit) { 
        if (!g2->nxt[bit]) continue;
        if (!g1->nxt[bit]) g1->nxt[bit] = new Node();
        merge(g1->nxt[bit], g2->nxt[bit], ithBit - 1);
      }
    }
    delete g2;
  }

  int get(int value, int time) { 
    int ret = 0;
    
    auto g = root;
    for (int i = MAXBIT; i >= 0; --i) { 
      int bit = (value >> i & 1);
      if (g->nxt[bit ^ 1] && g->nxt[bit ^ 1]->time <= time) { 
        g = g->nxt[bit ^ 1];
        ret |= (1 << i);
        continue;
      } 
      if (g->nxt[bit] && g->nxt[bit]->time <= time) {
        g = g->nxt[bit];
        continue;
      }
      return 0;
    }

    return ret;
  }
} T[N];

int n = 1;
vector<int> ad[N];
int d[N], t[N];
vector<pair<int, int>> save[N];

int answer[N];
int sz[N];
void dfs(int u, int p = -1) { 
  for (const auto& v : ad[u]) { 
    dfs(v, u);
    sz[u] += sz[v] + 1;
  }

  sort(ad[u].begin(), ad[u].end(), [&](const auto& a, const auto& b) { 
    return sz[a] > sz[b];
  });

  bool goHeavy = false;
  for (const auto& v : ad[u]) { 
    if (!goHeavy) { 
      swap(T[u].root, T[v].root);
      goHeavy = true;
      continue;
    }
    T[u].merge(T[u].root, T[v].root);
  }
  T[u].add(d[u], t[u]);

  for (const auto& [x, time] : save[u]) {
    answer[time] = T[u].get(d[x], time);
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> q;
  for (int i = 1; i <= q; ++i) { 
    string type; cin >> type;
    if (type == "Add") { 
      int x, w; cin >> x >> w;
      n += 1;
      ad[x].push_back(n);
      d[n] = d[x] ^ w;
      t[n] = i;
    } else { 
      int x, y; cin >> x >> y;
      save[y].push_back({x, i});
    }
  }

  memset(answer, -1, sizeof answer);
  dfs(1);
  
  for (int i = 1; i <= q; ++i) 
    if (answer[i] != -1) cout << answer[i] << "\n";
}

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