Submission #499292

#	Time	Username	Problem	Language	Result	Execution time	Memory
499292		inksamurai	Klasika (COCI20_klasika)	C++17	110 / 110	2844 ms	475812 KiB

klasika

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3qplfh5 ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using tupiii=tuple<int,int,int>;
using pii=pair<int,int>;
using vi=vector<int>;
using vll=vector<long long>;

struct node{
	set<int> ids;
	int nxt[2]={-1,-1};
};

int main(){
_3qplfh5;
	int q;
	cin>>q;
	vec(tupiii) qry;
	int n=1;
	rep(_,q){
		string s;
		cin>>s;
		int t=0;
		if(s=="Add"){
			t=1;
			n++;
		}
		int _a,_b;
		cin>>_a>>_b;
		qry.pb({t,_a,_b});
	}
	vec(vec(pii)) adj(n);
	{
		int now=1;
		for(auto [t,_a,_b] : qry){
			if(t==1){
				adj[_a-1].pb({now,_b});
				adj[now].pb({_a-1,_b});
				now++;
			}
		}
	}
	//rabbit tour
	vi tin(n,0),tout(n,0);
	vi psum(n,0);
	{
		int tm=0;
		auto dfs=[&](auto self,int v,int par)->void{
			tin[v]=tm++;
			for(auto edge : adj[v]){
				int u=edge.fi;
				if(u!=par){
					psum[u]=psum[v]^edge.se;
					self(self,u,v);
				}
			}
			tout[v]=tm++;
		};
		dfs(dfs,0,-1);
	}
	vec(node) rbts;
	rbts.pb({});
	auto add=[&](int v,int ai){
		int root=0;
		drep(j,31){
			bool x=ai&(1<<j);
			if(rbts[root].nxt[x]==-1){
				rbts[root].nxt[x]=sz(rbts);
				rbts.pb({});
			}
			root=rbts[root].nxt[x];
			rbts[root].ids.insert(tin[v]);
		}
	};
	auto get=[&](auto self,int root,int i,int ai,int _tin,int _tout)->int{
		if(i<0) return 0;
		bool x=ai&(1<<i);
		int neroot=rbts[root].nxt[x^1];
		if(neroot==-1){
			return self(self,rbts[root].nxt[x],i-1,ai,_tin,_tout);
		}else{
			auto it=rbts[neroot].ids.lower_bound(_tin);
			if(it!=rbts[neroot].ids.end() and *it<_tout){
				return self(self,neroot,i-1,ai,_tin,_tout)+(1<<i);
			}else{
				return self(self,rbts[root].nxt[x],i-1,ai,_tin,_tout);
			}
		}
	};
	int now=0;
	add(0,0);
	for(auto [t,_a,_b] : qry){
		if(t==0){
			_a--,_b--;
			int val=get(get,0,30,psum[_a],tin[_b],tout[_b]);
			cout<<val<<"\n";
		}else{
			now++;
			add(now,psum[now]);
		}
	}
//	
	return 0;
}

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