Submission #203228

#	Time	Username	Problem	Language	Result	Execution time	Memory
203228		luciocf	Klasika (COCI20_klasika)	C++14	0 / 110	181 ms	33168 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 2e5+10;
const int maxl = 20;

struct Q
{
	int op, u, v, vert;
} query[maxn];

struct Node
{
	Node *b[2];
	set<pii> S;
};

int n=1;

int path[maxn];

int st[maxn], en[maxn], tt;
int nivel[maxn], tab[maxn][maxl];

vector<int> grafo[maxn];

void dfs(int u, int p)
{
	st[u] = ++tt;

	for (auto v: grafo[u])
	{
		if (v != p)
		{
			tab[v][0] = u, nivel[v] = nivel[u]+1;
			dfs(v, u);
		}
	}
	
	en[u] = tt;
}

void build(void)
{
	for (int j = 1; j < maxl; j++)
		for (int i = 1; i <= n; i++)
			tab[i][j] = tab[tab[i][j-1]][j-1];
}

int lca(int u, int v)
{
	if (nivel[u] < nivel[v]) swap(u, v);

	for (int i = maxl-1; i >= 0; i--)
		if (nivel[u]-(1<<i) >= nivel[v])
			u = tab[u][i];

	if (u == v) return u;

	for (int i = maxl-1; i >= 0; i--)
		if (tab[u][i] && tab[v][i] && tab[u][i] != tab[v][i])
			u = tab[u][i], v = tab[v][i];

	return tab[u][0];  
}

void add(Node *t, int u, int v)
{
	Node *at = t;

	for (int i = 30; i >= 0; i--)
	{
		if (v&(1<<i))
		{
			if (!at->b[1]) at->b[1] = new Node();
			at = at->b[1];
		}
		else
		{
			if (!at->b[0]) at->b[0] = new Node();
			at = at->b[0];
		}

		at->S.insert({en[u], st[u]});
	}

}

int get_max(Node *t, int u, int v)
{
	Node *at = t;
	int ans = 0;

	for (int i = 30; i >= 0; i--)
	{
		Node *l = at->b[0], *r = at->b[1];

		if (v&(1<<i))
		{
			if (l == NULL)
			{
				at = r;
				continue;
			}

			set<pii>::iterator it = l->S.upper_bound({en[u], n+1});

			if (it == l->S.begin())
			{
				at = r;
				continue;
			}

			--it;

			if (it->second >= st[u])
			{
				ans += (1<<i);
				at = l;
			}
			else at = r;
		}
		else
		{
			if (r == NULL)
			{
				at = l;
				continue;
			}

			set<pii>::iterator it = r->S.upper_bound({en[u], n+1});

			if (it == r->S.begin())
			{
				at = l;
				continue;
			}

			--it;

			if (it->second >= st[u])
			{
				ans += (1<<i);
				at = r;
			}
			else at = l;
		}
	}

	return ans;
}

int main(void)
{
	int q;
	scanf("%d", &q);

	for (int i = 1; i <= q; i++)
	{
		string s;
		cin >> s;

		int u, v;
		scanf("%d %d", &u, &v);

		if (s[0] == 'A')
		{
			grafo[u].push_back(++n);
			grafo[n].push_back(u);

			path[n] = path[u]^v;

			query[i] = {0, u, v, n};
		}
		else query[i] = {1, u, v, 0};
	}

	dfs(1, 0);
	build();

	Node *root = new Node();

	for (int i = 1; i <= q; i++)
	{
		int u = query[i].u, v = query[i].v;

		if (query[i].op == 1)
		{
			int x = path[u]^path[lca(u, v)]^path[tab[v][0]];

			printf("%d\n", get_max(root, v, x));
		}
		else
			add(root, query[i].vert, path[query[i].vert]);
	}
}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:159:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
klasika.cpp:167:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

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