oj.uz

Submission #1017981

# Submission time Handle Problem Language Result Execution time Memory
1017981 2024-07-09T12:15:32 Z vjudge1 Klasika (COCI20_klasika) C++17
110 / 110
 4752 ms 483152 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 = 2500;

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

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

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;
			reverse(all(stk));
			while (!stk.empty())
				add(val[stk.back()],st[stk.back()]),stk.pop_back();
		}
	}
	
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 150516 KB Output is correct
2 Correct 59 ms 150736 KB Output is correct
3 Correct 60 ms 150612 KB Output is correct
4 Correct 60 ms 150608 KB Output is correct
5 Correct 59 ms 150652 KB Output is correct
6 Correct 60 ms 150752 KB Output is correct
7 Correct 67 ms 150708 KB Output is correct
8 Correct 72 ms 150756 KB Output is correct
9 Correct 73 ms 150612 KB Output is correct
10 Correct 61 ms 150612 KB Output is correct
11 Correct 61 ms 150676 KB Output is correct
12 Correct 63 ms 150740 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 150516 KB Output is correct
2 Correct 59 ms 150736 KB Output is correct
3 Correct 60 ms 150612 KB Output is correct
4 Correct 60 ms 150608 KB Output is correct
5 Correct 59 ms 150652 KB Output is correct
6 Correct 60 ms 150752 KB Output is correct
7 Correct 67 ms 150708 KB Output is correct
8 Correct 72 ms 150756 KB Output is correct
9 Correct 73 ms 150612 KB Output is correct
10 Correct 61 ms 150612 KB Output is correct
11 Correct 61 ms 150676 KB Output is correct
12 Correct 63 ms 150740 KB Output is correct
13 Correct 61 ms 150724 KB Output is correct
14 Correct 59 ms 150608 KB Output is correct
15 Correct 62 ms 150720 KB Output is correct
16 Correct 75 ms 150672 KB Output is correct
17 Correct 76 ms 150864 KB Output is correct
18 Correct 65 ms 150608 KB Output is correct
19 Correct 61 ms 150612 KB Output is correct
20 Correct 60 ms 150816 KB Output is correct
21 Correct 61 ms 150608 KB Output is correct
22 Correct 61 ms 150864 KB Output is correct
23 Correct 61 ms 150612 KB Output is correct
24 Correct 62 ms 150748 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 193732 KB Output is correct
2 Correct 965 ms 231044 KB Output is correct
3 Correct 1664 ms 264324 KB Output is correct
4 Correct 2778 ms 303068 KB Output is correct
5 Correct 719 ms 204740 KB Output is correct
6 Correct 1351 ms 284580 KB Output is correct
7 Correct 2450 ms 370288 KB Output is correct
8 Correct 4178 ms 483152 KB Output is correct
9 Correct 607 ms 191768 KB Output is correct
10 Correct 1174 ms 229768 KB Output is correct
11 Correct 1811 ms 261472 KB Output is correct
12 Correct 3110 ms 298916 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 150516 KB Output is correct
2 Correct 59 ms 150736 KB Output is correct
3 Correct 60 ms 150612 KB Output is correct
4 Correct 60 ms 150608 KB Output is correct
5 Correct 59 ms 150652 KB Output is correct
6 Correct 60 ms 150752 KB Output is correct
7 Correct 67 ms 150708 KB Output is correct
8 Correct 72 ms 150756 KB Output is correct
9 Correct 73 ms 150612 KB Output is correct
10 Correct 61 ms 150612 KB Output is correct
11 Correct 61 ms 150676 KB Output is correct
12 Correct 63 ms 150740 KB Output is correct
13 Correct 61 ms 150724 KB Output is correct
14 Correct 59 ms 150608 KB Output is correct
15 Correct 62 ms 150720 KB Output is correct
16 Correct 75 ms 150672 KB Output is correct
17 Correct 76 ms 150864 KB Output is correct
18 Correct 65 ms 150608 KB Output is correct
19 Correct 61 ms 150612 KB Output is correct
20 Correct 60 ms 150816 KB Output is correct
21 Correct 61 ms 150608 KB Output is correct
22 Correct 61 ms 150864 KB Output is correct
23 Correct 61 ms 150612 KB Output is correct
24 Correct 62 ms 150748 KB Output is correct
25 Correct 622 ms 193732 KB Output is correct
26 Correct 965 ms 231044 KB Output is correct
27 Correct 1664 ms 264324 KB Output is correct
28 Correct 2778 ms 303068 KB Output is correct
29 Correct 719 ms 204740 KB Output is correct
30 Correct 1351 ms 284580 KB Output is correct
31 Correct 2450 ms 370288 KB Output is correct
32 Correct 4178 ms 483152 KB Output is correct
33 Correct 607 ms 191768 KB Output is correct
34 Correct 1174 ms 229768 KB Output is correct
35 Correct 1811 ms 261472 KB Output is correct
36 Correct 3110 ms 298916 KB Output is correct
37 Correct 782 ms 194140 KB Output is correct
38 Correct 1134 ms 231352 KB Output is correct
39 Correct 1992 ms 266652 KB Output is correct
40 Correct 3097 ms 302960 KB Output is correct
41 Correct 1187 ms 205580 KB Output is correct
42 Correct 2041 ms 289504 KB Output is correct
43 Correct 3029 ms 363436 KB Output is correct
44 Correct 4752 ms 467668 KB Output is correct
45 Correct 818 ms 192264 KB Output is correct
46 Correct 1281 ms 229940 KB Output is correct
47 Correct 1859 ms 259824 KB Output is correct
48 Correct 3007 ms 299036 KB Output is correct