Submission #405234

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
405234	2021-05-16T02:42:37 Z	ngpin04	Klasika (COCI20_klasika)	C++14	110 / 110	2631 ms	426532 KB

klasika

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 2e5 + 5; 

struct node {
	set <int> s;
	node* ptr[2];

	node() {
		s.clear();
		ptr[0] = ptr[1] = nullptr;
	}
};

node *root = new node();

vector <int> adj[N];
 
pair <int, int> pir[N];

int tin[N];
int val[N];
int tout[N];
int n = 1,q,timer;
 
string op[N];

int getbit(int x, int i) {
	return (x >> i) & 1;
}

void dfs(int u) {
	tin[u] = ++timer;
	for (int v : adj[u])
		dfs(v);
	tout[u] = timer;
}

void add(int x, int id) {
	node* cur = root;

	for (int i = 29; i >= 0; i--) {
		node* &p = cur->ptr[getbit(x, i)];
		if (p == nullptr) 
			p = new node();
		cur = p;
		cur->s.insert(id);
	}
}

int getmax(int x, int l, int r) {
	node *cur = root;
	int res = 0;
	for (int i = 29; i >= 0; i--) {
		bool found = false;
		for (int val = 1; val >= 0; val--) {
			node *p = cur->ptr[val ^ getbit(x, i)];

			if (p == nullptr)
				continue;
			auto it = p->s.lower_bound(l);
			if (it == p->s.end() || *it > r)
				continue;

			found = true;
			res |= (val << i);
			cur = p;
			break;
		}
		if (!found)
			return -1;
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> q;
	for (int i = 1; i <= q; i++) 
		cin >> op[i] >> pir[i].fi >> pir[i].se;
	
	for (int i = 1; i <= q; i++) if (op[i] == "Add") {
		val[++n] = val[pir[i].fi] ^ pir[i].se;
		adj[pir[i].fi].push_back(n);
		pir[i].fi = n;
	}	
 
	dfs(1);

	add(val[1], tin[1]);
	for (int i = 1; i <= q; i++) {
		if (op[i] == "Add")
			add(val[pir[i].fi], tin[pir[i].fi]);
		else {
			int l = tin[pir[i].se];
			int r = tout[pir[i].se];
			cout << getmax(val[pir[i].fi], l, r) << "\n";
		} 

	}
	return 0;
}

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	11468 KB	Output is correct
2	Correct	7 ms	11468 KB	Output is correct
3	Correct	7 ms	11596 KB	Output is correct
4	Correct	7 ms	11724 KB	Output is correct
5	Correct	7 ms	11340 KB	Output is correct
6	Correct	7 ms	11468 KB	Output is correct
7	Correct	7 ms	11596 KB	Output is correct
8	Correct	9 ms	11724 KB	Output is correct
9	Correct	7 ms	11340 KB	Output is correct
10	Correct	7 ms	11596 KB	Output is correct
11	Correct	7 ms	11724 KB	Output is correct
12	Correct	7 ms	11724 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	11468 KB	Output is correct
2	Correct	7 ms	11468 KB	Output is correct
3	Correct	7 ms	11596 KB	Output is correct
4	Correct	7 ms	11724 KB	Output is correct
5	Correct	7 ms	11340 KB	Output is correct
6	Correct	7 ms	11468 KB	Output is correct
7	Correct	7 ms	11596 KB	Output is correct
8	Correct	9 ms	11724 KB	Output is correct
9	Correct	7 ms	11340 KB	Output is correct
10	Correct	7 ms	11596 KB	Output is correct
11	Correct	7 ms	11724 KB	Output is correct
12	Correct	7 ms	11724 KB	Output is correct
13	Correct	12 ms	12620 KB	Output is correct
14	Correct	14 ms	13880 KB	Output is correct
15	Correct	13 ms	15052 KB	Output is correct
16	Correct	14 ms	16196 KB	Output is correct
17	Correct	10 ms	12484 KB	Output is correct
18	Correct	12 ms	13772 KB	Output is correct
19	Correct	13 ms	15004 KB	Output is correct
20	Correct	14 ms	16088 KB	Output is correct
21	Correct	13 ms	12548 KB	Output is correct
22	Correct	12 ms	13772 KB	Output is correct
23	Correct	13 ms	14968 KB	Output is correct
24	Correct	14 ms	16076 KB	Output is correct

Subtask #3
33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	652 ms	122684 KB	Output is correct
2	Correct	1207 ms	225240 KB	Output is correct
3	Correct	1647 ms	323540 KB	Output is correct
4	Correct	2206 ms	426000 KB	Output is correct
5	Correct	755 ms	124060 KB	Output is correct
6	Correct	1213 ms	225644 KB	Output is correct
7	Correct	1688 ms	322724 KB	Output is correct
8	Correct	2179 ms	420184 KB	Output is correct
9	Correct	714 ms	123856 KB	Output is correct
10	Correct	1193 ms	226520 KB	Output is correct
11	Correct	1710 ms	324984 KB	Output is correct
12	Correct	2222 ms	421756 KB	Output is correct

Subtask #4
44.0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	11468 KB	Output is correct
2	Correct	7 ms	11468 KB	Output is correct
3	Correct	7 ms	11596 KB	Output is correct
4	Correct	7 ms	11724 KB	Output is correct
5	Correct	7 ms	11340 KB	Output is correct
6	Correct	7 ms	11468 KB	Output is correct
7	Correct	7 ms	11596 KB	Output is correct
8	Correct	9 ms	11724 KB	Output is correct
9	Correct	7 ms	11340 KB	Output is correct
10	Correct	7 ms	11596 KB	Output is correct
11	Correct	7 ms	11724 KB	Output is correct
12	Correct	7 ms	11724 KB	Output is correct
13	Correct	12 ms	12620 KB	Output is correct
14	Correct	14 ms	13880 KB	Output is correct
15	Correct	13 ms	15052 KB	Output is correct
16	Correct	14 ms	16196 KB	Output is correct
17	Correct	10 ms	12484 KB	Output is correct
18	Correct	12 ms	13772 KB	Output is correct
19	Correct	13 ms	15004 KB	Output is correct
20	Correct	14 ms	16088 KB	Output is correct
21	Correct	13 ms	12548 KB	Output is correct
22	Correct	12 ms	13772 KB	Output is correct
23	Correct	13 ms	14968 KB	Output is correct
24	Correct	14 ms	16076 KB	Output is correct
25	Correct	652 ms	122684 KB	Output is correct
26	Correct	1207 ms	225240 KB	Output is correct
27	Correct	1647 ms	323540 KB	Output is correct
28	Correct	2206 ms	426000 KB	Output is correct
29	Correct	755 ms	124060 KB	Output is correct
30	Correct	1213 ms	225644 KB	Output is correct
31	Correct	1688 ms	322724 KB	Output is correct
32	Correct	2179 ms	420184 KB	Output is correct
33	Correct	714 ms	123856 KB	Output is correct
34	Correct	1193 ms	226520 KB	Output is correct
35	Correct	1710 ms	324984 KB	Output is correct
36	Correct	2222 ms	421756 KB	Output is correct
37	Correct	1242 ms	126516 KB	Output is correct
38	Correct	1723 ms	228424 KB	Output is correct
39	Correct	2165 ms	329468 KB	Output is correct
40	Correct	2513 ms	426532 KB	Output is correct
41	Correct	1410 ms	124632 KB	Output is correct
42	Correct	1888 ms	225728 KB	Output is correct
43	Correct	2214 ms	322948 KB	Output is correct
44	Correct	2547 ms	419368 KB	Output is correct
45	Correct	1521 ms	124116 KB	Output is correct
46	Correct	2060 ms	226428 KB	Output is correct
47	Correct	2440 ms	323780 KB	Output is correct
48	Correct	2631 ms	421764 KB	Output is correct

Submission #405234

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 22.0 / 22.0

Subtask #3 33.0 / 33.0

Subtask #4 44.0 / 44.0

Subtask #1
11.0 / 11.0

Subtask #2
22.0 / 22.0

Subtask #3
33.0 / 33.0

Subtask #4
44.0 / 44.0