oj.uz

Submission #405223

# Submission time Handle Problem Language Result Execution time Memory
405223 2021-05-16T01:41:11 Z ngpin04 Klasika (COCI20_klasika) C++14
33 / 110
 890 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 <vector <int>> ptr;

	trie() {
		node = 0;
		ptr.assign(1, vector <int> (2, 0));
	}

	void add(int x) {
		int cur = 0;
		for (int i = 29; i >= 0; i--) {
			int &p = ptr[cur][getbit(x, i)];
			if (!p) {
				p = ++node;
				ptr.push_back(vector <int> (2, 0));
			}
			cur = p;
		}
	}

	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[cur][val ^ getbit(x, i)];
				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 124 ms 87008 KB Output is correct
2 Correct 129 ms 87364 KB Output is correct
3 Correct 148 ms 87944 KB Output is correct
4 Correct 150 ms 88444 KB Output is correct
5 Correct 149 ms 86824 KB Output is correct
6 Correct 170 ms 87256 KB Output is correct
7 Correct 148 ms 87748 KB Output is correct
8 Correct 154 ms 88620 KB Output is correct
9 Correct 148 ms 86852 KB Output is correct
10 Correct 169 ms 87600 KB Output is correct
11 Correct 150 ms 88040 KB Output is correct
12 Correct 151 ms 88772 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 87008 KB Output is correct
2 Correct 129 ms 87364 KB Output is correct
3 Correct 148 ms 87944 KB Output is correct
4 Correct 150 ms 88444 KB Output is correct
5 Correct 149 ms 86824 KB Output is correct
6 Correct 170 ms 87256 KB Output is correct
7 Correct 148 ms 87748 KB Output is correct
8 Correct 154 ms 88620 KB Output is correct
9 Correct 148 ms 86852 KB Output is correct
10 Correct 169 ms 87600 KB Output is correct
11 Correct 150 ms 88040 KB Output is correct
12 Correct 151 ms 88772 KB Output is correct
13 Correct 168 ms 92976 KB Output is correct
14 Correct 173 ms 100196 KB Output is correct
15 Correct 188 ms 107960 KB Output is correct
16 Correct 200 ms 116152 KB Output is correct
17 Correct 162 ms 92600 KB Output is correct
18 Correct 175 ms 99956 KB Output is correct
19 Correct 194 ms 107376 KB Output is correct
20 Correct 205 ms 114804 KB Output is correct
21 Correct 166 ms 92624 KB Output is correct
22 Correct 182 ms 99944 KB Output is correct
23 Correct 193 ms 107324 KB Output is correct
24 Correct 200 ms 114964 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 890 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 87008 KB Output is correct
2 Correct 129 ms 87364 KB Output is correct
3 Correct 148 ms 87944 KB Output is correct
4 Correct 150 ms 88444 KB Output is correct
5 Correct 149 ms 86824 KB Output is correct
6 Correct 170 ms 87256 KB Output is correct
7 Correct 148 ms 87748 KB Output is correct
8 Correct 154 ms 88620 KB Output is correct
9 Correct 148 ms 86852 KB Output is correct
10 Correct 169 ms 87600 KB Output is correct
11 Correct 150 ms 88040 KB Output is correct
12 Correct 151 ms 88772 KB Output is correct
13 Correct 168 ms 92976 KB Output is correct
14 Correct 173 ms 100196 KB Output is correct
15 Correct 188 ms 107960 KB Output is correct
16 Correct 200 ms 116152 KB Output is correct
17 Correct 162 ms 92600 KB Output is correct
18 Correct 175 ms 99956 KB Output is correct
19 Correct 194 ms 107376 KB Output is correct
20 Correct 205 ms 114804 KB Output is correct
21 Correct 166 ms 92624 KB Output is correct
22 Correct 182 ms 99944 KB Output is correct
23 Correct 193 ms 107324 KB Output is correct
24 Correct 200 ms 114964 KB Output is correct
25 Runtime error 890 ms 524292 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -