oj.uz

Submission #405221

# Submission time Handle Problem Language Result Execution time Memory
405221 2021-05-16T01:28:07 Z ngpin04 Klasika (COCI20_klasika) C++14
0 / 110
 927 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 (l >= u && 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);

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

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 86980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 86980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 927 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 Incorrect 125 ms 86980 KB Output isn't correct
2 Halted 0 ms 0 KB -