#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#define getar(ar,n) for(int i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define br cout<<"\n"
#define pb push_back
#define nl '\n'
#define fi first
#define se second
const int mxN = 3e5 + 50;
int N=1,idx=0,parent[mxN],depth[mxN],heavy[mxN],head[mxN],sz[mxN],lt[mxN],tin[mxN],tout[mxN],seg[mxN*4],val[mxN],till[mxN];
vector<pair<int,int>> adj[mxN];
vector<pair<int,int>> nadj[mxN];
struct Node {
Node* children[2];
Node(){
for(int i=0;i<2;++i){
children[i]=NULL;
}
}
};
struct Trie{
Node* root = new Node();
void add(int x){
Node* curr=root;
for(int i=32;i>=0;--i){
int curr_bit=(x&(1ll<<i))>0;
if(curr->children[curr_bit]==NULL){
curr->children[curr_bit]=new Node();
}
curr=curr->children[curr_bit];
}
}
int qry(int x){
Node* curr=root;
int ans=0;
for(int i=32;i>=0;--i){
int curr_bit=((x&(1ll<<i))>0);
if(curr->children[!curr_bit]!=NULL){
curr=curr->children[!curr_bit];
ans|=(1ll<<i);
}else{
curr=curr->children[curr_bit];
}
if(curr==NULL) break;
}
return ans;
}
} t[mxN*4];
struct Seg {
void update_1(int node,int start,int end,int idx,int val){
if(start==end){
seg[node]=val;
return;
}
int mid=start+(end-start)/2;
if(idx<=mid) update_1(node*2+1,start,mid,idx,val);
else update_1(node*2+2,mid+1,end,idx,val);
seg[node]=seg[node*2+1]^seg[node*2+2];
}
void update_2(int node,int start,int end,int idx,int val){
t[node].add(val);
if(start==end) return;
int mid=start+(end-start)/2;
if(idx<=mid) update_2(node*2+1,start,mid,idx,val);
else update_2(node*2+2,mid+1,end,idx,val);
}
int qry_answer(int node,int start,int end,int l,int r,int val){
if(start==end) return t[node].qry(val);
int mid=start+(end-start)/2;
if(r<=mid) return qry_answer(node*2+1,start,mid,l,r,val);
else if(l>mid) return qry_answer(node*2+2,mid+1,end,l,r,val);
else return max(qry_answer(node*2+1,start,mid,l,mid,val),qry_answer(node*2+2,mid+1,end,mid+1,r,val));
}
int xor_qry(int node,int start,int end,int l,int r){
if(start>r||end<l) return 0;
if(start>=l&&end<=r) return seg[node];
int mid=start+(end-start)/2;
return xor_qry(node*2+1,start,mid,l,r)^xor_qry(node*2+2,mid+1,end,l,r);
}
} seg_tree;
struct HLD {
void dfs(int u=1,int par=0){
sz[u]=1;
parent[u]=par;
depth[u]=depth[par]+1;
for(auto it:adj[u]){
if(it.fi^par){
dfs(it.fi,u);
val[it.fi]=it.se;
sz[u]+=sz[it.fi];
if(sz[heavy[u]]<sz[it.fi]) heavy[u]=it.fi;
}
}
}
void dfsHLD(int u=1,int chain=1){
head[u]=chain;
lt[idx]=val[u];
tin[u]=idx++;
seg_tree.update_1(0,0,N-1,tin[u],val[u]);
if(heavy[u]!=0) dfsHLD(heavy[u],chain);
for(auto it:adj[u]){
if(it.fi!=parent[u]&&it.fi!=heavy[u]) dfsHLD(it.fi,it.fi);
}
tout[u]=idx-1;
}
int path_xor(int u,int v){
int ans=0;
while(head[u]!=head[v]){
if(depth[head[u]]<depth[head[v]]) swap(u,v);
ans=ans^seg_tree.xor_qry(0,0,N-1,tin[head[u]],tin[u]);
u=parent[head[u]];
}
if(depth[u]<depth[v]) swap(u,v);
return (ans^seg_tree.xor_qry(0,0,N-1,tin[v],tin[u]))^val[v];
}
} hld;
int cdfs(int u,int path,int current){
int ans=current^path;
for(auto it:nadj[u]){
ans=max(ans,cdfs(it.fi,path,current^it.se));
}
return ans;
}
void lets_go() {
int q,u,v;cin>>q;
string type;
vector<vector<int>> Q; // 1-> add ,0-> query
for(int i=0;i<q;++i){
cin>>type>>u>>v;
if(type=="Add"){
Q.pb({1,u,++N,v});
adj[u].pb({N,v});
}else{
Q.pb({0,u,v});
}
}
hld.dfs();
hld.dfsHLD();
for(auto it:Q){
if(it[0]==1){
till[it[2]]=till[it[1]]^it[3];
nadj[it[1]].pb({it[2],it[3]});
//seg_tree.update_2(0,0,N-1,tin[it[2]],till[it[2]]);
}else{
u=it[1],v=it[2];
//show(seg_tree.qry_answer(0,0,N-1,tin[v],tout[v],hld.path_xor(u,v)^till[v]));
show(cdfs(v,hld.path_xor(u,v),0));
}
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
lets_go();
return 0;
}
Compilation message (stderr)
klasika.cpp:23:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
23 | #pragma GCC optimize("-fwhole-program")
| ^
klasika.cpp:30:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
30 | #pragma GCC optimize("-fstrict-overflow")
| ^
klasika.cpp:32:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
klasika.cpp:46:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
46 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
klasika.cpp:67:14: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
67 | Node(){
| ^
klasika.cpp:67:14: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
klasika.cpp:67:14: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
klasika.cpp:67:14: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
klasika.cpp:76:23: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
76 | void add(int x){
| ^
klasika.cpp:76:23: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
klasika.cpp:76:23: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
klasika.cpp:76:23: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
klasika.cpp:86:22: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
86 | int qry(int x){
| ^
klasika.cpp:86:22: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
klasika.cpp:86:22: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
klasika.cpp:86:22: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
klasika.cpp:104:59: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
104 | void update_1(int node,int start,int end,int idx,int val){
| ^
klasika.cpp:104:59: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
klasika.cpp:104:59: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
klasika.cpp:104:59: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
klasika.cpp:114:59: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
114 | void update_2(int node,int start,int end,int idx,int val){
| ^
klasika.cpp:114:59: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
klasika.cpp:114:59: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
klasika.cpp:114:59: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
klasika.cpp:121:64: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
121 | int qry_answer(int node,int start,int end,int l,int r,int val){
| ^
klasika.cpp:121:64: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
klasika.cpp:121:64: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
klasika.cpp:121:64: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
klasika.cpp:128:53: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
128 | int xor_qry(int node,int start,int end,int l,int r){
| ^
klasika.cpp:128:53: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
klasika.cpp:128:53: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
klasika.cpp:128:53: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
klasika.cpp:138:35: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
138 | void dfs(int u=1,int par=0){
| ^
klasika.cpp:138:35: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
klasika.cpp:138:35: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
klasika.cpp:138:35: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
klasika.cpp:152:40: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
152 | void dfsHLD(int u=1,int chain=1){
| ^
klasika.cpp:152:40: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
klasika.cpp:152:40: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
klasika.cpp:152:40: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
klasika.cpp:164:33: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
164 | int path_xor(int u,int v){
| ^
klasika.cpp:164:33: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
klasika.cpp:164:33: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
klasika.cpp:164:33: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
klasika.cpp:177:36: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
177 | int cdfs(int u,int path,int current){
| ^
klasika.cpp:177:36: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
klasika.cpp:177:36: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
klasika.cpp:177:36: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
klasika.cpp:185:14: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
185 | void lets_go() {
| ^
klasika.cpp:185:14: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
klasika.cpp:185:14: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
klasika.cpp:185:14: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
klasika.cpp:213:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
213 | signed main() {
| ^
klasika.cpp:213:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
klasika.cpp:213:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
klasika.cpp:213:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]| # | 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... |
