oj.uz

Submission #405224

# Submission time Handle Problem Language Result Execution time Memory
405224 2021-05-16T01:51:41 Z ngpin04 Klasika (COCI20_klasika) C++14
33 / 110
 1399 ms 524292 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 2e5 + 5; 
 
int getbit(int x, int i) {
	return (x >> i) & 1;
}
 
struct trie {
	int node;
	vector <int> ptr[2];
 
	trie() {
		node = 0;
		ptr[0].push_back(0);
		ptr[1].push_back(0);  
	}
 
	void add(int x) {
		int cur = 0;
		for (int i = 29; i >= 0; i--) {
			int &p = ptr[getbit(x, i)][cur];
			if (!p) {
				p = ++node;
				ptr[0].push_back(0);
				ptr[1].push_back(0);
			}
			cur = ptr[getbit(x, i)][cur]; 
		}
	}
 
	int getmax(int x) {
		int cur = 0;
		int res = 0;	
		for (int i = 29; i >= 0; i--) {
			bool found = false;
			for (int val = 1; val >= 0; val--) {
				int p = ptr[val ^ getbit(x, i)][cur];
				if (!p)
					continue;
				found = true;
				cur = p;
				res |= (val << i);
				break;
			}	
			if (!found)
				return -1;
		}
		return res;
	}
 
};
 
trie st[4 * N];
 
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];
 
void update(int id, int l, int r, int pos, int val) {
	if (l > pos || r < pos)
		return;
	st[id].add(val);
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	update(id << 1, l, mid, pos, val);
	update(id << 1 | 1, mid + 1, r, pos, val);
}
 
int getmax(int id, int l, int r, int u, int v, int val) {
	if (l > v || r < u)
		return -1;
	if (u <= l && r <= v) 
		return st[id].getmax(val);
	int mid = (l + r) >> 1;
	int lnode = getmax(id << 1, l, mid, u, v, val);
	int rnode = getmax(id << 1 | 1, mid + 1, r, u, v, val);
	return max(lnode, rnode);
}
 
void dfs(int u) {
	tin[u] = ++timer;
	for (int v : adj[u])
		dfs(v);
	tout[u] = timer;
}
 
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);
 
	update(1, 1, n, tin[1], val[1]);
	for (int i = 1; i <= q; i++) {
		if (op[i] == "Add") 
			update(1, 1, n, tin[pir[i].fi], val[pir[i].fi]);
		else {
			int l = tin[pir[i].se];
			int r = tout[pir[i].se];
			cout << getmax(1, 1, n, l, r, val[pir[i].fi]) << "\n";
		}
	}
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 105284 KB Output is correct
2 Correct 128 ms 105376 KB Output is correct
3 Correct 128 ms 105480 KB Output is correct
4 Correct 129 ms 105608 KB Output is correct
5 Correct 155 ms 105196 KB Output is correct
6 Correct 133 ms 105284 KB Output is correct
7 Correct 130 ms 105412 KB Output is correct
8 Correct 130 ms 105560 KB Output is correct
9 Correct 116 ms 105248 KB Output is correct
10 Correct 144 ms 105412 KB Output is correct
11 Correct 130 ms 105440 KB Output is correct
12 Correct 132 ms 105584 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 105284 KB Output is correct
2 Correct 128 ms 105376 KB Output is correct
3 Correct 128 ms 105480 KB Output is correct
4 Correct 129 ms 105608 KB Output is correct
5 Correct 155 ms 105196 KB Output is correct
6 Correct 133 ms 105284 KB Output is correct
7 Correct 130 ms 105412 KB Output is correct
8 Correct 130 ms 105560 KB Output is correct
9 Correct 116 ms 105248 KB Output is correct
10 Correct 144 ms 105412 KB Output is correct
11 Correct 130 ms 105440 KB Output is correct
12 Correct 132 ms 105584 KB Output is correct
13 Correct 148 ms 106380 KB Output is correct
14 Correct 139 ms 107740 KB Output is correct
15 Correct 143 ms 108780 KB Output is correct
16 Correct 141 ms 110660 KB Output is correct
17 Correct 133 ms 106436 KB Output is correct
18 Correct 142 ms 107732 KB Output is correct
19 Correct 167 ms 108648 KB Output is correct
20 Correct 159 ms 110512 KB Output is correct
21 Correct 135 ms 106252 KB Output is correct
22 Correct 140 ms 107648 KB Output is correct
23 Correct 173 ms 108660 KB Output is correct
24 Correct 143 ms 110312 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 258004 KB Output is correct
2 Correct 1268 ms 419232 KB Output is correct
3 Runtime error 1399 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 105284 KB Output is correct
2 Correct 128 ms 105376 KB Output is correct
3 Correct 128 ms 105480 KB Output is correct
4 Correct 129 ms 105608 KB Output is correct
5 Correct 155 ms 105196 KB Output is correct
6 Correct 133 ms 105284 KB Output is correct
7 Correct 130 ms 105412 KB Output is correct
8 Correct 130 ms 105560 KB Output is correct
9 Correct 116 ms 105248 KB Output is correct
10 Correct 144 ms 105412 KB Output is correct
11 Correct 130 ms 105440 KB Output is correct
12 Correct 132 ms 105584 KB Output is correct
13 Correct 148 ms 106380 KB Output is correct
14 Correct 139 ms 107740 KB Output is correct
15 Correct 143 ms 108780 KB Output is correct
16 Correct 141 ms 110660 KB Output is correct
17 Correct 133 ms 106436 KB Output is correct
18 Correct 142 ms 107732 KB Output is correct
19 Correct 167 ms 108648 KB Output is correct
20 Correct 159 ms 110512 KB Output is correct
21 Correct 135 ms 106252 KB Output is correct
22 Correct 140 ms 107648 KB Output is correct
23 Correct 173 ms 108660 KB Output is correct
24 Correct 143 ms 110312 KB Output is correct
25 Correct 739 ms 258004 KB Output is correct
26 Correct 1268 ms 419232 KB Output is correct
27 Runtime error 1399 ms 524292 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -