Submission #256834

#	Time	Username	Problem	Language	Result	Execution time	Memory
256834		MrRobot_28	Klasika (COCI20_klasika)	C++17	110 / 110	3066 ms	439048 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;
	set <pair <int, int> > s;
	node(){
	left = NULL;
	right = NULL;};
};
void update(node* &w, int i, int val, int v)
{
	if(i < 0)
	{
		return;
	}
	if(val & (1 << i))
	{
		if(!w -> right)
		{
			w -> right = new node();
		}
		node* &t = w -> right;
		t -> s.insert({tin[v], v});
		update(t, i - 1, val, v);
	}
	else
	{
		if(!w -> left)
		{
			w -> left = new node();
		}
		node* &t = w -> left;
		t -> s.insert({tin[v], v});
		update(t, i - 1, val, v);
	}
}
int ans(node* w, int i, int val, int l, int r)
{
	if(i < 0)
	{
		return 0;
	}
	int val1 = (1 << 31) - 1 - val;
	if(val1 & (1 << i))
	{
		if(!w -> right)
		{
			return ans(w -> left, i - 1, val, l, r);
		}
		else
		{
			set <pair <int, int> > :: iterator it;
			it = w -> right -> s.lower_bound({l, 0});
			if(it != w -> right -> s.end() && it -> first <= r)
			{
				return ans(w -> right, i - 1, val, l, r) + (1 << i);
			}
			else
			{
				return ans(w -> left, i - 1, val, l, r);
			}
		}
	}
	else
	{
		if(!w -> left)
		{
			return ans(w -> right, i - 1, val, l, r) + (1 << i);
		}
		else
		{
			set <pair <int, int> > :: iterator it;
			it = w -> left -> s.lower_bound({l, 0});
			if(it != w -> left -> s.end() && it -> first <= r)
			{
				return ans(w -> left, i - 1, val, l, r);
			}
			else
			{
				return ans(w -> right, i - 1, val, l, r) + (1 << i);
			}
		}
	}
}
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);
	node* tree = new node();
	cnt = 1;
	update(tree, 30, 0, 0);
	for(int i = 0; i < q; i++)
	{
		if(type[i] == "Add")
		{
			update(tree, 30, h[cnt], cnt);
			cnt++;
		}
		else
		{
			mass[i].first--;
			mass[i].second--;
			int val = h[mass[i].first];
			int val1 = ans(tree, 30, val, tin[mass[i].second], tout[mass[i].second]);
			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++)
                 ~~^~~~~~~~~~~~~
klasika.cpp: In function 'int ans(node*, int, int, int, int)':
klasika.cpp:64:23: warning: integer overflow in expression [-Woverflow]
  int val1 = (1 << 31) - 1 - val;
             ~~~~~~~~~~^~~

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