#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
#define ff first
#define ss second
const ll K = 2;
struct Vertex {
ll to[K];
set<ll>inds;
Vertex() {
for (ll i = 0; i < K; i++) {
to[i] = -1;
}
}
};
ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll LG = 30;
ll n, m, k;
vector<Vertex>p(1);
vector<pair<ll, ll>>q;
vector<pair<ll, ll>>g[N];
ll vl[N];
ll ind[N];
ll sz[N];
ll timer = 0;
void dfs(ll v, ll val = 0, ll par = -1) {
sz[v] = 1;
ind[v] = timer++;
if (par != -1) {
vl[v] = vl[par] ^ val;
}
for (ll i = 0; i < g[v].size(); i++) {
ll to = g[v][i].ff;
ll w = g[v][i].ss;
if (to != par) {
dfs(to, w, v);
sz[v] += sz[to];
}
}
}
void add(ll x, ll i) {
ll v = 0;
p[v].inds.insert(i);
for (ll j = LG; j >= 0; j--) {
ll c = 0;
if (x & (1ll << j)) {
c = 1;
}
if (p[v].to[c] == -1) {
p[v].to[c] = p.size();
p.emplace_back();
}
p[p[v].to[c]].inds.insert(i);
//cout << v << ": " << p[v].to[0] << " " << p[v].to[1] << endl;
v = p[v].to[c];
}
}
ll get_ans(ll x, ll i) {
ll v = 0;
ll ans = 0;
for (ll j = LG; j >= 0; j--) {
if (x & (1ll << j)) {
if (p[v].to[0] != -1) {
auto it = p[p[v].to[0]].inds.lower_bound(ind[i]);
//cout << res << " 1 ";
if ((it != p[p[v].to[0]].inds.end()) && (*it < ind[i] + sz[i])) {
v = p[v].to[0];
ans += (1ll << j);
}
else {
v = p[v].to[1];
}
}
else {
v = p[v].to[1];
}
}
else {
if (p[v].to[1] != -1) {
auto it = p[p[v].to[1]].inds.lower_bound(ind[i]);
//cout << res << " 2 ";
if ((it != p[p[v].to[1]].inds.end()) && (*it < ind[i] + sz[i])) {
v = p[v].to[1];
ans += (1ll << j);
}
else {
v = p[v].to[0];
}
}
else {
v = p[v].to[0];
}
}
}
//cout << endl;
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
ll cur = 2;
vl[1] = 0;
for (ll i = 0; i < n; i++) {
ll x, y;
string tp;
cin >> tp >> x >> y;
if (tp == "Add") {
g[x].push_back({ cur,y });
q.push_back({ -1,cur });
cur++;
}
else {
q.push_back({ x,y });
}
}
dfs(1);
/*for (ll i = 1; i <= n; i++) {
cout << i << ": " << vl[i] << endl;
}
cout << endl;*/
for (ll i = 0; i < n; i++) {
if (q[i].ff == -1) {
ll v = q[i].ss;
//cout << "ADDING: " << v << endl;
add(vl[v], ind[v]);
//cout << "HASA STE\n";
}
else {
cout << get_ans(vl[q[i].ff], q[i].ss) << endl;
}
}
return 0;
}
/// ---- - -------- ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - -------- ------ -------- -- - - -
Compilation message
klasika.cpp: In function 'void dfs(ll, ll, ll)':
klasika.cpp:61:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (ll i = 0; i < g[v].size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
882 ms |
129460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
