#include <bits/stdc++.h>
#pragma GCC target("popcnt")
using namespace std;
typedef long long ll;
#define block 450
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];
template<class T> struct Trie {
struct Node {
int cntl=0;
int cntr=0;
int l = -1, r = -1;
};
int B;
int t;
vector<Node> nodes;
int newNode() {
nodes.emplace_back();
return nodes.size() - 1;
}
void init(int _B) {
B = _B;
nodes.clear();
newNode();
}
void insert(int n) {
int u = 0;
for (int i = B; i >= 0; i--) {
if ((n >> i) & 1) {
if (nodes[u].r == -1) {
nodes[u].r = newNode();
}
nodes[u].cntr++;
u = nodes[u].r;
}
else {
if (nodes[u].l == -1) {
nodes[u].l = newNode();
}
nodes[u].cntl++;
u = nodes[u].l;
}
}
}
ll query(int n) {
int u = 0;
ll ans = 0;
for (int i = B; i >= 0; i--) {
if ((n >> i) & 1) {
if (nodes[u].l != -1) {
u = nodes[u].l;
ans += (1ll << i);
} else {
u = nodes[u].r;
}
} else {
if (nodes[u].r != -1 ) {
u = nodes[u].r;
ans+=(1ll << i);
} else {
u = nodes[u].l;
}
}
}
return ans;
}
};
Trie<int>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;
dp[v] = dp[u] xor adj[u][i].second;
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});
query.push_back({s,{u,node}});
}
else{
query.push_back({s,{u,w}});
}
}
dfs(1,0);
for(int i = 0; i <= block; i++) trie[i].init(30);
for(int i = 1; i <= n; i++){
blk[i] = i / block;
}
memset(to, -1, sizeof(to));
for(int i = 0; i < query.size(); i++){
pii v = query[i].second;
string s = query[i].first;
//cout<<s<<' '<<v.first<<' '<<v.second<<endl;
if(s == "Add"){
trie[blk[v.second]].insert(dp[v.second]);
to[in[v.second]] = dp[v.second];
}
else{
int start = in[v.second];
int end = out[v.second];
if(blk[start] == blk[end]){
long long ans = 0;
for(int j = start; j <= end; j++){
if(to[j] < 0) continue;
ans = max(ans, dp[v.first] xor to[j]);
}
printf("%lld\n",ans);
}
else{
long long ans = 0;
for(int j = blk[start] + 1; j < blk[end]; j++){
ans = max(ans, trie[j].query(dp[v.first]));
}
for(int j = start; j / block == blk[start]; j++){
if(to[j] < 0) continue;
ans = max(ans, dp[v.first] xor to[j]);
}
for(int j = end; j / block == blk[end]; j--){
if(to[j] < 0) 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:84: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]
84 | for(int i = 0; i < adj[u].size(); i++){
| ~~^~~~~~~~~~~~~~~
klasika.cpp: In function 'int main()':
klasika.cpp:93:14: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
93 | scanf("%d",&q);
| ~^ ~~
| | |
| | long long int*
| int*
| %lld
klasika.cpp:112: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]
112 | for(int i = 0; i < query.size(); i++){
| ~~^~~~~~~~~~~~~~
klasika.cpp:93:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6612 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6612 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5103 ms |
44816 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6612 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
