Submission #256807

#	Time	Username	Problem	Language	Result	Execution time	Memory
256807		MrRobot_28	Klasika (COCI20_klasika)	C++17	33 / 110	1041 ms	524292 KiB

klasika

#include<bits/stdc++.h>
 
using namespace std;
int n = 1;
vector <vector <pair <int, int> > > g;
vector <int> h, tin, tout;
int timer = 0;
void dfs(int v, int p = -1)
{
	tin[v] = timer++;
	for(int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].first;
		int w = g[v][i].second;
		if(to != p)
		{
			h[to] = h[v] ^ w;
			dfs(to, v);
		}
	}
	tout[v] = timer - 1;
}
struct node{
	node* left;
	node* right;
	node(){
	left = NULL;
	right = NULL;};
};
vector <node*> tree;
void go_down(node* &w, int i, int val)
{
	if(i < 0)
	{
		return;
	}
	if(val & (1LL << i))
	{
		if(!w -> right)
		{
			w -> right = new node();
		}
		go_down(w -> right, i - 1, val);
	}
	else
	{
		if(!w -> left)
		{
			w -> left = new node();
		}
		go_down(w -> left, i - 1, val);
	}
}
void update(int v, int l, int r, int ind, int val)
{
	go_down(tree[v], 30, val);
	if(l == r)
	{
		return;
	}
	if(ind <= (r + l) / 2)
	{
		update(v * 2, l, (r + l) / 2, ind, val);
	}
	else
	{
		update(v * 2 + 1, (r + l) / 2 + 1, r, ind, val);
	}
}
int ans(int v, int l, int r, int al, int ar, int val)
{
	if(l >= al && r <= ar)
	{
		if(!tree[v] -> left && !tree[v] -> right)
		{
			return val;
		}
		int val1 = (1LL << 31) - val - 1;
		node* w = tree[v];
		int valans = 0;
		for(int i = 30; i >= 0; i--)
		{
			if(val1 & (1LL << i))
			{
				if(!w -> right)
				{
					w = w -> left;
				}
				else
				{
					w = w -> right;
					valans += (1LL << i);
				}
			}
			else
			{
				if(!w -> left)
				{
					w = w -> right;
					valans += (1LL << i);
				}
				else
				{
					w = w -> left;
				}
			}
		}
		return valans;
	}
	else if(l <= ar && r >= al)
	{
		int t1 = ans(v * 2, l, (r + l) / 2, al, ar, val);
		int t2 = ans(v * 2 + 1, (r + l) / 2 + 1, r, al, ar, val);
		if((t1 ^ val) > (t2 ^ val))
		{
			return t1;
		}
		return t2;
	}
	else
	{
		return val;
	}
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int q;
	cin >> q;
	vector <string> type(q);
	vector <pair <int, int> > mass(q);
	for(int i = 0; i < q; i++){
		cin >> type[i];
		cin >> mass[i].first >> mass[i].second;
		if(type[i] == "Add"){
			n++;
		}
	}
	g.resize(n);
	h.resize(n);
	tin.resize(n);
	tout.resize(n);
	int cnt = 1;
	for(int i = 0; i < q; i++)
	{
		if(type[i] == "Add")
		{
			mass[i].first--;
			g[mass[i].first].push_back({cnt, mass[i].second});
			cnt++;
		}
	}
	dfs(0);
	tree.resize(4 * n);
	for(int i = 0; i < 4 * n; i++){
		tree[i] = new node();
	}
	cnt = 1;
	update(1, 0, n - 1, tin[0], 0);
	for(int i = 0; i < q; i++)
	{
		if(type[i] == "Add")
		{
			update(1, 0, n - 1, tin[cnt], h[cnt]);
			cnt++;
		}
		else
		{
			mass[i].first--;
			mass[i].second--;
			int val = h[mass[i].first];
			int val1 = ans(1, 0, n - 1, tin[mass[i].second], tout[mass[i].second], val);
			cout << (val ^ val1) << "\n";
		}
	}
	return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:11:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[v].size(); i++)
                 ~~^~~~~~~~~~~~~

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