Submission #1173146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173146		rayan_bd	Klasika (COCI20_klasika)	C++17	33 / 110	680 ms	589824 KiB

klasika

#include <bits/stdc++.h>
using namespace std;

#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 = 2e5 + 500;

int N=1,idx=0,parent[mxN],depth[mxN],heavy[mxN],head[mxN],sz[mxN],tin[mxN],tout[mxN],seg[mxN*4],val[mxN],till[mxN];
vector<pair<int,int>> adj[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=30;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=30;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;
	}
};

unordered_map<int,Trie> t;

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];
  }
  // O(32logN)
  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>r||end<l) return 0;
  	if(start>=l&&end<=r) return t[node].qry(val);
  	int mid=start+(end-start)/2;
  	return max(qry_answer(node*2+1,start,mid,l,r,val),qry_answer(node*2+2,mid+1,end,l,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;
		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;

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();
	t[0].add(0);
	for(auto it:Q){
		if(it[0]==1){
			till[it[2]]=till[it[1]]^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]));
		}
	}
}

signed main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    

    lets_go();

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44