oj.uz

Submission #203239

# Submission time Handle Problem Language Result Execution time Memory
203239 2020-02-19T21:42:52 Z luciocf Klasika (COCI20_klasika) C++14
110 / 110
 3325 ms 432724 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 2e5+10;

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;

vector<int> grafo[maxn];

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

	for (auto v: grafo[u])
		if (v != p)
			dfs(v, u);
	
	en[u] = tt;
}

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({st[u], en[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.lower_bound({st[u], 0});

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

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

			set<pii>::iterator it = r->S.lower_bound({st[u], 0});

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

			if (it->second <= en[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);

	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)
			printf("%d\n", get_max(root, v, path[u]));
		else
			add(root, query[i].vert, path[query[i].vert]);
	}
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5240 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 8 ms 5500 KB Output is correct
4 Correct 10 ms 5628 KB Output is correct
5 Correct 9 ms 5112 KB Output is correct
6 Correct 9 ms 5240 KB Output is correct
7 Correct 9 ms 5368 KB Output is correct
8 Correct 8 ms 5624 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct
11 Correct 8 ms 5496 KB Output is correct
12 Correct 9 ms 5496 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5240 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 8 ms 5500 KB Output is correct
4 Correct 10 ms 5628 KB Output is correct
5 Correct 9 ms 5112 KB Output is correct
6 Correct 9 ms 5240 KB Output is correct
7 Correct 9 ms 5368 KB Output is correct
8 Correct 8 ms 5624 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct
11 Correct 8 ms 5496 KB Output is correct
12 Correct 9 ms 5496 KB Output is correct
13 Correct 12 ms 6520 KB Output is correct
14 Correct 14 ms 7800 KB Output is correct
15 Correct 16 ms 9080 KB Output is correct
16 Correct 17 ms 10232 KB Output is correct
17 Correct 13 ms 6392 KB Output is correct
18 Correct 14 ms 7672 KB Output is correct
19 Correct 16 ms 8952 KB Output is correct
20 Correct 17 ms 10104 KB Output is correct
21 Correct 15 ms 6488 KB Output is correct
22 Correct 14 ms 7672 KB Output is correct
23 Correct 16 ms 8952 KB Output is correct
24 Correct 17 ms 10108 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1006 ms 120824 KB Output is correct
2 Correct 1725 ms 226304 KB Output is correct
3 Correct 2291 ms 327160 KB Output is correct
4 Correct 2899 ms 428536 KB Output is correct
5 Correct 971 ms 119288 KB Output is correct
6 Correct 1675 ms 223224 KB Output is correct
7 Correct 2262 ms 322808 KB Output is correct
8 Correct 2977 ms 422124 KB Output is correct
9 Correct 1025 ms 118776 KB Output is correct
10 Correct 1648 ms 223612 KB Output is correct
11 Correct 2293 ms 324600 KB Output is correct
12 Correct 2929 ms 423480 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5240 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 8 ms 5500 KB Output is correct
4 Correct 10 ms 5628 KB Output is correct
5 Correct 9 ms 5112 KB Output is correct
6 Correct 9 ms 5240 KB Output is correct
7 Correct 9 ms 5368 KB Output is correct
8 Correct 8 ms 5624 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct
11 Correct 8 ms 5496 KB Output is correct
12 Correct 9 ms 5496 KB Output is correct
13 Correct 12 ms 6520 KB Output is correct
14 Correct 14 ms 7800 KB Output is correct
15 Correct 16 ms 9080 KB Output is correct
16 Correct 17 ms 10232 KB Output is correct
17 Correct 13 ms 6392 KB Output is correct
18 Correct 14 ms 7672 KB Output is correct
19 Correct 16 ms 8952 KB Output is correct
20 Correct 17 ms 10104 KB Output is correct
21 Correct 15 ms 6488 KB Output is correct
22 Correct 14 ms 7672 KB Output is correct
23 Correct 16 ms 8952 KB Output is correct
24 Correct 17 ms 10108 KB Output is correct
25 Correct 1006 ms 120824 KB Output is correct
26 Correct 1725 ms 226304 KB Output is correct
27 Correct 2291 ms 327160 KB Output is correct
28 Correct 2899 ms 428536 KB Output is correct
29 Correct 971 ms 119288 KB Output is correct
30 Correct 1675 ms 223224 KB Output is correct
31 Correct 2262 ms 322808 KB Output is correct
32 Correct 2977 ms 422124 KB Output is correct
33 Correct 1025 ms 118776 KB Output is correct
34 Correct 1648 ms 223612 KB Output is correct
35 Correct 2293 ms 324600 KB Output is correct
36 Correct 2929 ms 423480 KB Output is correct
37 Correct 1726 ms 124824 KB Output is correct
38 Correct 2364 ms 229368 KB Output is correct
39 Correct 2839 ms 333304 KB Output is correct
40 Correct 3220 ms 432724 KB Output is correct
41 Correct 1777 ms 122744 KB Output is correct
42 Correct 2376 ms 226152 KB Output is correct
43 Correct 2774 ms 325880 KB Output is correct
44 Correct 3201 ms 424864 KB Output is correct
45 Correct 1930 ms 122040 KB Output is correct
46 Correct 2559 ms 227028 KB Output is correct
47 Correct 2938 ms 326632 KB Output is correct
48 Correct 3325 ms 427208 KB Output is correct