oj.uz

Submission #203234

# Submission time Handle Problem Language Result Execution time Memory
203234 2020-02-19T21:24:03 Z luciocf Klasika (COCI20_klasika) C++14
33 / 110
 3076 ms 430304 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({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);

	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:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
klasika.cpp:141: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 5244 KB Output is correct
3 Correct 8 ms 5496 KB Output is correct
4 Correct 10 ms 5496 KB Output is correct
5 Correct 8 ms 5112 KB Output is correct
6 Incorrect 9 ms 5368 KB Output isn't correct
7 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 5244 KB Output is correct
3 Correct 8 ms 5496 KB Output is correct
4 Correct 10 ms 5496 KB Output is correct
5 Correct 8 ms 5112 KB Output is correct
6 Incorrect 9 ms 5368 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1274 ms 120872 KB Output is correct
2 Correct 2185 ms 229172 KB Output is correct
3 Correct 2423 ms 330516 KB Output is correct
4 Correct 2981 ms 430304 KB Output is correct
5 Correct 986 ms 120952 KB Output is correct
6 Correct 1717 ms 224760 KB Output is correct
7 Correct 2244 ms 324252 KB Output is correct
8 Correct 3076 ms 423228 KB Output is correct
9 Correct 1008 ms 119756 KB Output is correct
10 Correct 1933 ms 224888 KB Output is correct
11 Correct 2387 ms 325616 KB Output is correct
12 Correct 2881 ms 423548 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 5244 KB Output is correct
3 Correct 8 ms 5496 KB Output is correct
4 Correct 10 ms 5496 KB Output is correct
5 Correct 8 ms 5112 KB Output is correct
6 Incorrect 9 ms 5368 KB Output isn't correct
7 Halted 0 ms 0 KB -