제출 #1138065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138065		arashmemar	Klasika (COCI20_klasika)	C++17	110 / 110	3453 ms	214040 KiB

klasika

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 100, sq = 2100, lg = 31;

int br[maxn], v;
vector <int> ne[maxn];
int st[maxn], ft[maxn], t, nov = 1, ar[maxn];
vector <pair <bool, pair<int, int>>> qs;
bool use[maxn];

struct T
{
	int vu, h;
	T *ch[2];

	T(int tmp)
	{
		ch[0] = ch[1] = NULL, vu = 0, h = tmp;
		return ;
	}

	void spread()
	{
		if (ch[0] == NULL and ch[1] == NULL)
		{
			ch[0] = new T(h + 1);
			ch[1] = new T(h + 1);
		}
		return ;
	}

	void update()
	{
		vu++;
		if (h == lg)
		{
			return ;
		}
		spread();
		int ind = lg - h - 1;
		ind = (((1 << ind) & v) > 0);
		ch[ind]->update();
		return ;
	}

	int get()
	{
		if (h == lg)
		{
			return 0;
		}	
		int ind = lg - h - 1;
		int indi = (((1 << ind) & v) > 0);
		bool wtg = !indi;

		if (ch[wtg] == NULL or !ch[wtg]->vu)
		{
			wtg = !wtg;
		}

		int ret = 0;

		ret += (1 << ind) * (wtg != indi);

		if (ch[wtg] != NULL)
		{
			ret += ch[wtg]->get();
		}

		return ret;
	}
};

T *rs[maxn / sq + 100];

void dfs(int v)
{
	st[v] = ++t;
	for (int i = 0;i < ne[v].size();i++)
	{
		int u = ne[v][i];
		dfs(u);
	}
	ft[v] = t;
	return ;
}



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int q;
	cin >> q;
	for (int i = 0;i < q;i++)
	{
		string com;
		int a, b;
		bool tmp;
		cin >> com >> a >> b;
		if (com == "Query")
		{
			tmp = 0;
		}
		else
		{
			tmp = 1;
		}
		if (tmp)
		{
			ne[a].push_back(++nov);
			ar[nov] = ar[a] ^ b;
			a = nov;
			b = ar[a];
		}
		qs.push_back({tmp, {a, b}});
	}

	dfs(1);

	for (int i = 0;i <= q / sq + 10;i++)
	{
		rs[i] = new T(0);
	}

	v = 0;

	rs[0]->update();
	use[1] = 1;

	for (auto o : qs)
	{
		bool com = o.first;
		int a = o.second.first, b = o.second.second;
		if (com)
		{
			v = b;
			rs[st[a] / sq]->update();
			br[st[a]] = b;
			use[st[a]] = 1;
		}
		else
		{
			int l = st[b], r = ft[b];
			int sql = l / sq + 1, sqr = r / sq;

			int ret = 0;

			v = ar[a];

			for (int i = sql;i < sqr;i++)
			{
				ret = max(ret, rs[i]->get());
			}

			for (int i = l;i <= r and i < sql * sq;i++)
			{
				if (use[i])
				{
					ret = max(ret, v ^ br[i]);
				}
			}
			if (sqr >= sql)
			{
				for (int i = sqr * sq;i <= r;i++)
				{
					if (use[i])
					{
						ret = max(ret, v ^ br[i]);
					}
				}
			}
			cout << ret << '\n';
		}
	}
}

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