Submission #462573

#	Time	Username	Problem	Language	Result	Execution time	Memory
462573		Jasiekstrz	Klasika (COCI20_klasika)	C++17	110 / 110	364 ms	157288 KiB

klasika

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
const int L=30;
struct Trie
{
	int mn_time;
	Trie *e[2];
};
const int TRIE_SIZE=N*(L+1)+10;
Trie triemem[TRIE_SIZE];
int trieit=0;
Trie* newtrie()
{
	return &triemem[trieit++];
}
int getmn_time(Trie* x)
{
	return (x==nullptr ? N+10:x->mn_time);
}
Trie* build(int c,int t,int l)
{
	Trie* rt=newtrie();
	rt->mn_time=t;
	if(l<0)
		return rt;
	bool tmp=(c&(1<<l));
	//cerr<<tmp<<" "<<c<<"\n";
	rt->e[tmp]=build(c,t,l-1);
	return rt;
}
Trie* merge(Trie* x,Trie* y)
{
	if(x==nullptr)
		return y;
	if(y==nullptr)
		return x;
	x->mn_time=min(x->mn_time,y->mn_time);
	for(int i:{0,1})
	{
		//cerr<<i<<" "<<getmn_time(x->e[i])<<" "<<getmn_time(y->e[i])<<"\n";
		x->e[i]=merge(x->e[i],y->e[i]);
	}
	return x;
}
int read(Trie* x,int c,int t,int l)
{
	if(l==-1)
		return c;
	bool tmp=(c&(1<<l));
	//cerr<<c<<" "<<t<<" "<<l<<" "<<tmp<<"\n";
	c|=(1<<l);
	if(getmn_time(x->e[!tmp])<t)
		return read(x->e[!tmp],c,t,l-1);
	c^=(1<<l);
	return read(x->e[tmp],c,t,l-1);
}

vector<pair<int,int>> que[N+10];
int tim[N+10];
vector<int> e[N+10];
int d[N+10];
int ans[N+10];
bool is_query[N+10];
Trie* dfs(int x)
{
	Trie* rt=build(d[x],tim[x],L);
	for(auto v:e[x])
	{
		auto tmp=dfs(v);
		rt=merge(rt,tmp);
	}
	for(auto [t,c]:que[x])
		ans[t]=read(rt,c,t,L);
	return rt;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int q,n=1;
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		string t;
		int a,b;
		cin>>t>>a>>b;
		if(t=="Add")
		{
			e[a].push_back(++n);
			d[n]=d[a]^b;
			tim[n]=i;
		}
		else
		{
			is_query[i]=true;
			que[b].emplace_back(i,d[a]);
		}
	}
	dfs(1);
	for(int i=1;i<=q;i++)
	{
		if(is_query[i])
			cout<<ans[i]<<"\n";
	}
	return 0;
}

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