This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 3e5+5;
const int M = (1<<17);
const ll inf = 1e15;
const ll mod = 1e15+7;
int n, t, k, m, d[N], in[N], out[N];
int ans, tong, a[N], b[N];
string s[N];
struct node
{
int x[2];
set<int> vi;
node(){}
node( int _x, int _y)
{
x[0] = _x;
x[1] = _y;
}
};
vector<node> q;
vector<int> adj[N], kq;
void add(int x, int y)
{
for(int i = 0, j = 30; j >= 0; j --)
{
int t = (x >> j & 1);
if(q[i].x[t] == 0)
{
q[i].x[t] = q.size();
q.pb(node(0, 0));
}
i = q[i].x[t];
q[i].vi.insert(y);
}
}
int get(int x, int l, int r)
{
int total = 0;
for(int i = 0, j = 30; j >= 0; j --)
{
int t = (x >> j & 1);
int nxt = q[i].x[t^1];
auto it = q[nxt].vi.lower_bound(l);
if(it != q[nxt].vi.end() && (*it) <= r)
{
i = nxt;
total += (1<<j);
}
else i = q[i].x[t];
}
return total;
}
void dfs(int u)
{
in[u] = ++k;
for(int v: adj[u])dfs(v);
out[u] = k;
}
void sol()
{
cin >> m;
n = 1;
for(int i = 1; i <= m; i ++)
{
cin >> s[i] >> a[i] >> b[i];
if(s[i] == "Add")
{
++n;
adj[a[i]].pb(n);
d[n] = d[a[i]] ^ b[i];
a[i] = n;
}
}
dfs(1);
q.pb(node(0, 0));
for(int i = 1; i <= m; i ++)
{
if(s[i] == "Add")
{
add(d[a[i]], in[a[i]]);
}
else cout << get(d[a[i]], in[b[i]], out[b[i]]) << '\n';
}
}
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
#define task "test"
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int ntest = 1;
//cin >> ntest;
while(ntest -- > 0)
sol();
}
Compilation message (stderr)
klasika.cpp: In function 'int main()':
klasika.cpp:103:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:104:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |