oj.uz

Submission #1017514

# Submission time Handle Problem Language Result Execution time Memory
1017514 2024-07-09T08:36:03 Z vjudge1 Klasika (COCI20_klasika) C++17
0 / 110
 11 ms 19544 KB 
#include <bits/stdc++.h>

using namespace std;

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

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

vector<int> nei[M],ver[M];
int nxt[M][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+=(1<<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()
{
	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[0]<=b)
				dfs1(b,val[a],ans);
			else
			{
				ans=get(val[a],st[b],en[b]);
				for (int i:pen)
					if (parr[i]==b ||(st[parr[i]]>=st[b] && st[parr[i]]<en[b]))
						ans=max(ans,val[i]);
			}
			cout<<ans<<endl;
		}
		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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 19544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 19544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 19544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 19544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -