Submission #1017955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017955		vjudge1	Klasika (COCI20_klasika)	C++17	66 / 110	4317 ms	490796 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) v.begin(), v.end()

const int M = 2e5 + 2, thres = 2500;

vector<int> nei[M],ver[M*31];
int nxt[M*31][2],val[M],st[M],en[M],sz,t,parr[M];
stack<int> stk;

void dfs(int u)
{
	st[u]=t++;
	for (int i:nei[u])
		dfs(i);
	en[u]=t;
	stk.push(u);
}

void add(int vl,int tm)
{
	int cur=0;
	for (int i=30;i>=0;i--)
	{
		int x=0;
		if ((1<<i)&vl)
			x=1;
		if (!nxt[cur][x])
			nxt[cur][x]=++sz;
		cur=nxt[cur][x];
		ver[cur].push_back(tm);
	}
}

int get(int vl,int s,int e)
{
	int cur=0,ans=0;
	for (int i=30;i>=0;i--)
	{
		int x=1;
		if ((1<<i)&vl)
			x=0;
		if (!nxt[cur][x])
			x=1-x;
		else if(lower_bound(all(ver[nxt[cur][x]]),s)==lower_bound(all(ver[nxt[cur][x]]),e))
			x=1-x;
		else
			ans+=(1LL<<i);
		cur=nxt[cur][x];
	}
	return ans;
}

void dfs1(int u,int vl,int &ans)
{
	ans=max(ans,val[u]^vl);
	for (int i:nei[u])
		dfs1(i,vl,ans);
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	int q;
	cin>>q;
	int nodes=2;
	vector<int> pen;
	while (q--)
	{
		string s;
		cin>>s;
		if (s=="Add")
		{
			int x,y;
			cin>>x>>y;
			val[nodes]=val[x]^y;
			pen.push_back(nodes);
			if (x<pen[0])
				parr[nodes]=x;
			else
				parr[nodes]=parr[x];
			nei[x].push_back(nodes++);
		}
		else
		{
			int a,b;
			cin>>a>>b;
			int ans=0;
			if (!pen.empty() && pen[0]<=b)
				dfs1(b,val[a],ans);
			else
			{
				if (nodes>thres)
					ans=get(val[a],st[b],en[b]);
				else
					ans=val[a];
				for (int i:pen)
				{
					if (parr[i]==b || (nodes>thres && st[parr[i]]>=st[b] && st[parr[i]]<en[b]))
						ans=max(ans,val[i]^val[a]);
				}
			}
			cout<<ans<<'\n';
		}
		if (pen.size()==thres)
		{
			for (int i=0;i<sz;i++)
				nxt[i][0]=nxt[i][1]=0,ver[i].clear();
			t=0;
			pen.clear();
			dfs(1);
			sz=0;
			while (!stk.empty())
				add(val[stk.top()],st[stk.top()]),stk.pop();
		}
	}
	
	return 0;
}

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