oj.uz

Submission #870957

# Submission time Handle Problem Language Result Execution time Memory
870957 2023-11-09T15:20:19 Z hungnt Klasika (COCI20_klasika) C++14
110 / 110
 2100 ms 463196 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29684 KB Output is correct
2 Correct 6 ms 29532 KB Output is correct
3 Correct 7 ms 29624 KB Output is correct
4 Correct 7 ms 29788 KB Output is correct
5 Correct 6 ms 29356 KB Output is correct
6 Correct 7 ms 29532 KB Output is correct
7 Correct 7 ms 29532 KB Output is correct
8 Correct 6 ms 29788 KB Output is correct
9 Correct 6 ms 29532 KB Output is correct
10 Correct 6 ms 29532 KB Output is correct
11 Correct 6 ms 29788 KB Output is correct
12 Correct 6 ms 29788 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29684 KB Output is correct
2 Correct 6 ms 29532 KB Output is correct
3 Correct 7 ms 29624 KB Output is correct
4 Correct 7 ms 29788 KB Output is correct
5 Correct 6 ms 29356 KB Output is correct
6 Correct 7 ms 29532 KB Output is correct
7 Correct 7 ms 29532 KB Output is correct
8 Correct 6 ms 29788 KB Output is correct
9 Correct 6 ms 29532 KB Output is correct
10 Correct 6 ms 29532 KB Output is correct
11 Correct 6 ms 29788 KB Output is correct
12 Correct 6 ms 29788 KB Output is correct
13 Correct 8 ms 30556 KB Output is correct
14 Correct 10 ms 32088 KB Output is correct
15 Correct 12 ms 33372 KB Output is correct
16 Correct 11 ms 34392 KB Output is correct
17 Correct 8 ms 30556 KB Output is correct
18 Correct 10 ms 31960 KB Output is correct
19 Correct 12 ms 33208 KB Output is correct
20 Correct 12 ms 34164 KB Output is correct
21 Correct 8 ms 30556 KB Output is correct
22 Correct 9 ms 31836 KB Output is correct
23 Correct 11 ms 33116 KB Output is correct
24 Correct 11 ms 34140 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 147496 KB Output is correct
2 Correct 1031 ms 255032 KB Output is correct
3 Correct 1356 ms 358964 KB Output is correct
4 Correct 1643 ms 462748 KB Output is correct
5 Correct 603 ms 145384 KB Output is correct
6 Correct 1026 ms 251428 KB Output is correct
7 Correct 1477 ms 352560 KB Output is correct
8 Correct 1960 ms 454344 KB Output is correct
9 Correct 559 ms 144972 KB Output is correct
10 Correct 923 ms 252496 KB Output is correct
11 Correct 1352 ms 354920 KB Output is correct
12 Correct 1667 ms 456084 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29684 KB Output is correct
2 Correct 6 ms 29532 KB Output is correct
3 Correct 7 ms 29624 KB Output is correct
4 Correct 7 ms 29788 KB Output is correct
5 Correct 6 ms 29356 KB Output is correct
6 Correct 7 ms 29532 KB Output is correct
7 Correct 7 ms 29532 KB Output is correct
8 Correct 6 ms 29788 KB Output is correct
9 Correct 6 ms 29532 KB Output is correct
10 Correct 6 ms 29532 KB Output is correct
11 Correct 6 ms 29788 KB Output is correct
12 Correct 6 ms 29788 KB Output is correct
13 Correct 8 ms 30556 KB Output is correct
14 Correct 10 ms 32088 KB Output is correct
15 Correct 12 ms 33372 KB Output is correct
16 Correct 11 ms 34392 KB Output is correct
17 Correct 8 ms 30556 KB Output is correct
18 Correct 10 ms 31960 KB Output is correct
19 Correct 12 ms 33208 KB Output is correct
20 Correct 12 ms 34164 KB Output is correct
21 Correct 8 ms 30556 KB Output is correct
22 Correct 9 ms 31836 KB Output is correct
23 Correct 11 ms 33116 KB Output is correct
24 Correct 11 ms 34140 KB Output is correct
25 Correct 631 ms 147496 KB Output is correct
26 Correct 1031 ms 255032 KB Output is correct
27 Correct 1356 ms 358964 KB Output is correct
28 Correct 1643 ms 462748 KB Output is correct
29 Correct 603 ms 145384 KB Output is correct
30 Correct 1026 ms 251428 KB Output is correct
31 Correct 1477 ms 352560 KB Output is correct
32 Correct 1960 ms 454344 KB Output is correct
33 Correct 559 ms 144972 KB Output is correct
34 Correct 923 ms 252496 KB Output is correct
35 Correct 1352 ms 354920 KB Output is correct
36 Correct 1667 ms 456084 KB Output is correct
37 Correct 1043 ms 148700 KB Output is correct
38 Correct 1472 ms 256000 KB Output is correct
39 Correct 1750 ms 361232 KB Output is correct
40 Correct 1858 ms 463196 KB Output is correct
41 Correct 1014 ms 145716 KB Output is correct
42 Correct 1500 ms 251564 KB Output is correct
43 Correct 1819 ms 353124 KB Output is correct
44 Correct 2100 ms 453424 KB Output is correct
45 Correct 1103 ms 145400 KB Output is correct
46 Correct 1625 ms 252068 KB Output is correct
47 Correct 1905 ms 354120 KB Output is correct
48 Correct 1992 ms 456700 KB Output is correct