oj.uz

Submission #405225

# Submission time Handle Problem Language Result Execution time Memory
405225 2021-05-16T01:54:14 Z ngpin04 Klasika (COCI20_klasika) C++14
33 / 110
 1193 ms 524288 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;
 
	trie() {
		node = 0;
		ptr.push_back(0);
		ptr.push_back(0);  
	}
 
	void add(int x) {
		int cur = 0;
		for (int i = 29; i >= 0; i--) {
			int &p = ptr[cur << 1 | getbit(x, i)];
			if (!p) {
				p = ++node;
				ptr.push_back(0);
				ptr.push_back(0);
			}
			cur = ptr[cur << 1 | getbit(x, i)];
		}
	}
 
	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 b = val ^ getbit(x, i);
				int p = ptr[cur << 1 | b];
				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 102 ms 61380 KB Output is correct
2 Correct 93 ms 61544 KB Output is correct
3 Correct 102 ms 61600 KB Output is correct
4 Correct 100 ms 61740 KB Output is correct
5 Correct 102 ms 61384 KB Output is correct
6 Correct 89 ms 61408 KB Output is correct
7 Correct 100 ms 61628 KB Output is correct
8 Correct 101 ms 61812 KB Output is correct
9 Correct 99 ms 61420 KB Output is correct
10 Correct 100 ms 61600 KB Output is correct
11 Correct 103 ms 61572 KB Output is correct
12 Correct 142 ms 61864 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 61380 KB Output is correct
2 Correct 93 ms 61544 KB Output is correct
3 Correct 102 ms 61600 KB Output is correct
4 Correct 100 ms 61740 KB Output is correct
5 Correct 102 ms 61384 KB Output is correct
6 Correct 89 ms 61408 KB Output is correct
7 Correct 100 ms 61628 KB Output is correct
8 Correct 101 ms 61812 KB Output is correct
9 Correct 99 ms 61420 KB Output is correct
10 Correct 100 ms 61600 KB Output is correct
11 Correct 103 ms 61572 KB Output is correct
12 Correct 142 ms 61864 KB Output is correct
13 Correct 106 ms 62476 KB Output is correct
14 Correct 108 ms 63864 KB Output is correct
15 Correct 109 ms 64948 KB Output is correct
16 Correct 111 ms 66788 KB Output is correct
17 Correct 128 ms 62512 KB Output is correct
18 Correct 107 ms 63908 KB Output is correct
19 Correct 108 ms 64816 KB Output is correct
20 Correct 116 ms 66472 KB Output is correct
21 Correct 106 ms 62484 KB Output is correct
22 Correct 111 ms 63720 KB Output is correct
23 Correct 109 ms 64832 KB Output is correct
24 Correct 130 ms 66432 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 210432 KB Output is correct
2 Correct 940 ms 369916 KB Output is correct
3 Runtime error 1193 ms 524288 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 102 ms 61380 KB Output is correct
2 Correct 93 ms 61544 KB Output is correct
3 Correct 102 ms 61600 KB Output is correct
4 Correct 100 ms 61740 KB Output is correct
5 Correct 102 ms 61384 KB Output is correct
6 Correct 89 ms 61408 KB Output is correct
7 Correct 100 ms 61628 KB Output is correct
8 Correct 101 ms 61812 KB Output is correct
9 Correct 99 ms 61420 KB Output is correct
10 Correct 100 ms 61600 KB Output is correct
11 Correct 103 ms 61572 KB Output is correct
12 Correct 142 ms 61864 KB Output is correct
13 Correct 106 ms 62476 KB Output is correct
14 Correct 108 ms 63864 KB Output is correct
15 Correct 109 ms 64948 KB Output is correct
16 Correct 111 ms 66788 KB Output is correct
17 Correct 128 ms 62512 KB Output is correct
18 Correct 107 ms 63908 KB Output is correct
19 Correct 108 ms 64816 KB Output is correct
20 Correct 116 ms 66472 KB Output is correct
21 Correct 106 ms 62484 KB Output is correct
22 Correct 111 ms 63720 KB Output is correct
23 Correct 109 ms 64832 KB Output is correct
24 Correct 130 ms 66432 KB Output is correct
25 Correct 551 ms 210432 KB Output is correct
26 Correct 940 ms 369916 KB Output is correct
27 Runtime error 1193 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -