oj.uz

Submission #203231

# Submission time Handle Problem Language Result Execution time Memory
203231 2020-02-19T21:10:11 Z luciocf Klasika (COCI20_klasika) C++14
33 / 110
 3287 ms 445672 KB 
#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;

	Node()
	{
		b[0] = b[1] = NULL;
	}
};

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();
	add(root, 1, 0);

	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[v];

			if (lca(u, v) == u) x = path[u];

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

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
klasika.cpp:172: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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5240 KB Output is correct
2 Correct 8 ms 5344 KB Output is correct
3 Correct 8 ms 5496 KB Output is correct
4 Correct 8 ms 5624 KB Output is correct
5 Incorrect 8 ms 5240 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5240 KB Output is correct
2 Correct 8 ms 5344 KB Output is correct
3 Correct 8 ms 5496 KB Output is correct
4 Correct 8 ms 5624 KB Output is correct
5 Incorrect 8 ms 5240 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1372 ms 124184 KB Output is correct
2 Correct 2082 ms 236072 KB Output is correct
3 Correct 2674 ms 340508 KB Output is correct
4 Correct 3287 ms 445672 KB Output is correct
5 Correct 1066 ms 125432 KB Output is correct
6 Correct 1761 ms 232776 KB Output is correct
7 Correct 2341 ms 335864 KB Output is correct
8 Correct 3012 ms 439048 KB Output is correct
9 Correct 1107 ms 124792 KB Output is correct
10 Correct 1805 ms 233464 KB Output is correct
11 Correct 2441 ms 337872 KB Output is correct
12 Correct 3075 ms 440372 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5240 KB Output is correct
2 Correct 8 ms 5344 KB Output is correct
3 Correct 8 ms 5496 KB Output is correct
4 Correct 8 ms 5624 KB Output is correct
5 Incorrect 8 ms 5240 KB Output isn't correct
6 Halted 0 ms 0 KB -