Submission #870957

#	Time	Username	Problem	Language	Result	Execution time	Memory
870957		hungnt	Klasika (COCI20_klasika)	C++14	110 / 110	2100 ms	463196 KiB

klasika

#include<bits/stdc++.h>
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

const int N = 1e6 + 5;

struct node
{
	set<int> s;
	node *child[2];
	node()
	{
		child[0] = child[1] = NULL;
	}
};

struct Trie
{
	node *root;
	Trie() {
		root = new node();
	}
	void add(int value, int id)
	{
		node *p = root;
		for (int i = 30; i >= 0; i--)
        {
			int c = BIT(value, i);
			if (p->child[c] == NULL) p->child[c] = new node();
			p = p->child[c];
			p->s.insert(id);
		}
	}
	int get(int value, int L, int R)
	{
		int ans = 0;
		node *p = root;
		for (int i = 30; i >= 0; i--)
        {
			int c = BIT(value, i);
			c ^= 1;
			if (p->child[c] == NULL || p->child[c]->s.lower_bound(L) == p->child[c]->s.upper_bound(R)) p = p->child[c ^ 1];
			else
			{
				ans += (1 << i);
				p = p->child[c];
			}
		}
		return ans;
	}
} trie;

struct Query
{
	int type, x, y;
};

vector<pair<int, int>> adj[N];
int Start[N], End[N], Rxor[N];
vector<Query> Q;
int Time = 0;

void dfs(int u, int p, int L)
{
	Start[u] = ++Time;
	Rxor[u] = L;
	for (auto [v, w] : adj[u])
        if (v != p)
            dfs(v, u, w ^ L);
	End[u] = Time;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n = 1;
	int q;
	string s;
    int x, y;
	cin >> q;
	while (q--)
    {
		cin >> s;
		cin >> x >> y;
		if (s[0] == 'A')
		{
			Q.push_back({0, ++n, y});
			adj[x].push_back({n, y});
			adj[n].push_back({x, y});
		}
        else Q.push_back({1, x, y});
	}

	dfs(1, -1, 0);
	trie.add(0, Start[1]);

	for (auto [type, x, y] : Q)
    {
		if (type == 0) trie.add(Rxor[x], Start[x]);
		else cout << trie.get(Rxor[x], Start[y], End[y]) << "\n";
	}

	return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'void dfs(int, int, int)':
klasika.cpp:67:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |  for (auto [v, w] : adj[u])
      |            ^
klasika.cpp: In function 'int main()':
klasika.cpp:98:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |  for (auto [type, x, y] : Q)
      |            ^

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