Submission #1284900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284900		quan606303	Klasika (COCI20_klasika)	C++20	110 / 110	365 ms	196524 KiB

klasika

///0-0 : what is your motivation, quan606303?
///quan606303 : Hutao
/*idea : 



*/
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
using namespace std;
const int MOD=1e9+7;
const int maxn=2e5+7;
vector<int> adj[maxn];
int q,n=1;
struct trie_node
{
	int min_tm;
	trie_node *s[2];
};
int ti[maxn];
vector<int> T[maxn];
pair<int,int> query[maxn];
int d[maxn];
int ans[maxn];
trie_node *trie[maxn];
trie_node *create_node()
{
	trie_node *node=new trie_node();
	node->min_tm=1e18;
	for (int i=0;i<2;i++)node->s[i]=NULL;
	return node;
}
void add(int cnt,int x,int tm)
{
	trie_node *node=trie[cnt];
	//cout<<cnt<<"--"<<tm<<endl;
	for (int i=30;i>=0;i--)
	{
		bool index=(x&(1LL<<i));
		if (node->s[index]==NULL)node->s[index]=create_node();
		node=node->s[index];
		node->min_tm=min(node->min_tm,tm);
		//cout<<index<<" ";
	}
	//cout<<endl;
}
int get(int x,int id,int cnt)
{
	trie_node *node=trie[cnt];
	int res=0;
	//cout<<"batdau"<<cnt<<" "<<id<<" "<<x<<endl;
	for (int i=30;i>=0;i--)
	{
		bool index=(x&(1LL<<i));
		if (node->s[!index]!=NULL&&node->s[!index]->min_tm<id)
		{
			node=node->s[!index];
			res|=(1<<i);
			//cout<<index<<" "<<res<<" "<<node->min_tm<<endl;;
		}
		else if (node->s[index]!=NULL&&node->s[index]->min_tm<id)
		{
			//if (node->s[!index]!=NULL)cout<<node->s[!index]->min_tm<<" ";
			node=node->s[index];
			//cout<<index<<" "<<endl;
		}
		else 
		{
			return 0;
		}
	}
	//cout<<endl;
	return res;
}
int child[maxn];
void merge(trie_node *x,trie_node *y)
{
	y->min_tm=min(y->min_tm,x->min_tm);
	if (x->s[0]!=NULL)
	{
		if (y->s[0]==NULL)y->s[0]=x->s[0];
		else merge(x->s[0],y->s[0]);
	}
	if (x->s[1]!=NULL)
	{
		if (y->s[1]==NULL)y->s[1]=x->s[1];
		else merge(x->s[1],y->s[1]);
	}
}
void dfs(int u)
{
	child[u]=1;
	trie[u]=create_node();
	add(u,d[u],ti[u]);
	for (auto v:adj[u])
	{
		dfs(v);
		if (child[u]<child[v])
		{
			swap(child[u],child[v]);
			swap(trie[u],trie[v]);
		}
		merge(trie[v],trie[u]);
		
		child[u]+=child[v];
	}
	for (auto id:T[u])ans[id]=get(d[query[id].fi],id,u);
}
int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>q;
	for (int i=1;i<=q;i++)
	{
		string type;
		int x,y;
		cin>>type>>x>>y;
		if (type[0]=='A')
		{
			n++;
			d[n]=(d[x]^y);
			adj[x].push_back(n);
			query[i]={n,-1};
		}
		else query[i]={x,y};
	}
	for (int i=1;i<=q;i++)
	{
		if (query[i].se==-1)
		{
			//cout<<query[i].fi<<" "<<i<<endl;
			ti[query[i].fi]=i;
		}
		else T[query[i].se].push_back(i);
	}
	dfs(1);
	for (int i=1;i<=q;i++)if (query[i].se!=-1)cout<<ans[i]<<endl;
	return 0;
}

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