#include<bits/stdc++.h>
using namespace std;
#define ft first
#define sd second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
struct nodes{
set<int> left_ids;
int one, zero;
nodes(){
one = zero = -1;
}
};
int n, t, last = 1;
vector<nodes> trie(10000005);
vector<pii> edges[1000000];
vector< pair<int, pii> > query;
int l[1000000], r[1000000], x[1000000];
bitset<200001> vis;
void dfs(int p, int node, int val){
//cout << p << " " << node << "\n";
if(vis[node]) return;
vis[node] = true;
l[node] = t++;
x[node] = x[p]^val;
//cout << "xor node : " << node << " " << x[node] << "\n";
for(int i=0; i<edges[node].size(); i++){
dfs(node, edges[node][i].ft, edges[node][i].sd);
}
r[node] = t++;
}
void new_node(int node, int idx, int bit){
//cout << "node : " << node << " idx : " << idx << " bit : " << bit << "\n";
trie[node].left_ids.insert(l[idx]);
if( bit < 0 ) return;
//cout << ( x[idx]&(1<<bit) ) << "\n";
if(x[idx] & (1<<bit)){
if( trie[node].one == -1 )
trie[node].one = last ++;
new_node(trie[node].one, idx, bit -1);
}
else{
if( trie[node].zero == -1 )
trie[node].zero = last ++;
new_node(trie[node].zero, idx, bit -1);
}
}
bool ask_node(int node, int b){
return (trie[node].left_ids.lower_bound(l[b]) != trie[node].left_ids.lower_bound(r[b]));
}
int traverse(int mxor, int b, int bit, int node){
if( bit < 0 || last == 1) return 0;
if( mxor & (1<<bit) ){
if( trie[node].zero != -1 && ask_node(trie[node].zero, b) ){
//cout << "0 " << trie[node].zero << " add\n";
return traverse(mxor, b, bit -1, trie[node].zero);
}
else{
//cout << "1 " << trie[node].one << "\n";
return (1<<bit) + traverse(mxor, b, bit -1, trie[node].one);
}
}
else{
if( trie[node].one != -1 && ask_node(trie[node].one, b) ){
//cout << "1 " << trie[node].one << " add\n";
return (1<<bit) + traverse(mxor, b, bit -1, trie[node].one);
}
else{
//cout << "0 " << trie[node].zero << "\n";
return traverse(mxor, b, bit -1, trie[node].zero);
}
}
return 0;
}
int ans_query(int a, int b){
//cout << "xa " << x[a] << "\n";
return x[a] ^ traverse(x[a], b, 30, 0);
}
int main(){
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
int Q; cin >> Q;
n = 1;
for(int q=0; q<Q; q++){
string s; cin >> s;
if(s == "Add"){
int x, y; cin >> x >> y;
//query.resize(query.size() +1);
query.pb( mp( 0, mp(x, y) ) );
//edges[x].resize(edges[x].size() +1);
edges[x].pb( mp(++n, y) );
}
else{
int a, b; cin >> a >> b;
//query.resize(query.size() +1);
query.pb( mp( 1, mp(a, b) ) );
}
}
//cout << "ok\n";
vis.reset();
dfs(0, 1, 0);
//cout << "ok\n";
n = 1;
for(int i=0; i<Q; i++){
if(query[i].ft == 0){
n++; new_node(0, n, 30);
//for(int j=0; j<last; j++)
// cout << trie[j].zero << " " << trie[j].one << "\n";
}
else{
//cout << "query\n";
cout << ans_query(query[i].sd.ft, query[i].sd.sd) << "\n";
}
}
}
Compilation message
klasika.cpp: In function 'void dfs(int, int, int)':
klasika.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<edges[node].size(); i++){
~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
272 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
272 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
271 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
272 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
