#include <bits/stdc++.h>
#pragma GCC target("popcnt")
using namespace std;
typedef long long ll;
#define block 467
typedef pair<int,int> pii;
const int sz = 4e5 + 1;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int mod = (1 << 32);
long long n,m,k,q,x;
vector<pii>adj[N + 1];
vector<pair<string,pii>>query;
int timer = 1;
int in[N + 1],out[N + 1];
long long dp[N + 1];
long long blk[N + 1];
long long to[N + 1];
bool vis[N + 1];
template<class T> struct Trie {
struct Node {
Node *c[2];
};
Node *root = new Node();
void insert(int x){
Node *cur = root;
for(int i = 30; i >= 0; i--){
if(x&(1<<i)){
if(!cur->c[1]) cur->c[1] = new Node();
cur = cur->c[1];
} else {
if(!cur->c[0]) cur->c[0] = new Node();
cur = cur->c[0];
}
}
}
long long query(int x){
long long res = 0;
Node *cur = root;
for(int i = 30; i >= 0; i--){
if(x&(1<<i)){
if(cur->c[0]){
res += (1<<i);
cur = cur->c[0];
}
else cur = cur->c[1];
} else {
if(cur->c[1]){
res += (1<<i);
cur = cur->c[1];
}
else cur = cur->c[0];
}
}
return res;
}
};
Trie<long long>trie[block + 1];
void dfs(int u,int p){
in[u] = timer++;
for(int i = 0; i < adj[u].size(); i++){
int v = adj[u][i].first;
if(v == p) continue;
dfs(v,u);
}
out[u] = timer - 1;
}
int main(){
scanf("%d",&q);
int node = 1;
for(int i = 1; i <= q; i++){
string s; int u,w;
cin >> s >> u >> w;
if(s == "Add"){
adj[u].push_back({++node,w});
dp[node] = dp[u] xor w;
query.push_back({s,{u,node}});
}
else{
query.push_back({s,{u,w}});
}
}
dfs(1,0);
vis[1] = 1;
for(int i = 0; i < query.size(); i++){
pii v = query[i].second;
string s = query[i].first;
if(s == "Add"){
trie[blk[v.second]].insert(dp[v.second]);
to[in[v.second]] = dp[v.second];
vis[in[v.second]] = 1;
}
else{
int start = in[v.second] ;
int end = out[v.second];
int bkstart = start / block;
int bkend = end / block;
if(start == end){
printf("%lld\n",(dp[v.first] xor dp[v.second]));
continue;
}
if(bkstart = bkend){
long long ans = 0;
for(int j = start; j <= end; j++){
if(!vis[j]) continue;
ans = max(ans, dp[v.first] xor to[j]);
}
printf("%lld\n",ans);
}
else{
long long ans = 0;
for(int j = bkstart + 1; j < bkend; j++){
ans = max(ans, trie[j].query(dp[v.first]));
}
for(int j = start; j / block == bkstart; j++){
if(!vis[j]) continue;
ans = max(ans, dp[v.first] xor to[j]);
}
for(int j = end; j / block == bkend ; j--){
if(!vis[j]) continue;
ans = max(ans, dp[v.first] xor to[j]);
}
printf("%lld\n",ans);
}
}
}
return 0;
}
Compilation message
klasika.cpp:10:20: warning: left shift count >= width of type [-Wshift-count-overflow]
10 | const int mod = (1 << 32);
| ~~^~~~~
klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:62:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 0; i < adj[u].size(); i++){
| ~~^~~~~~~~~~~~~~~
klasika.cpp: In function 'int main()':
klasika.cpp:70:14: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
70 | scanf("%d",&q);
| ~^ ~~
| | |
| | long long int*
| int*
| %lld
klasika.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::__cxx11::basic_string<char>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i = 0; i < query.size(); i++){
| ~~^~~~~~~~~~~~~~
klasika.cpp:103:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
103 | if(bkstart = bkend){
| ~~~~~~~~^~~~~~~
klasika.cpp:70:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5009 ms |
37616 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
