oj.uz

Submission #405231

# Submission time Handle Problem Language Result Execution time Memory
405231 2021-05-16T02:10:56 Z ngpin04 Klasika (COCI20_klasika) C++14
33 / 110
 920 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 <set <int>> pos;
	vector <vector <int>> ptr;
 
	trie(int n) {
		node = 0;
		ptr.assign(30 * n + 5, vector <int> (2, 0));  
		pos.resize(n + 5);
	}
 
	void add(int x, int id) {
		int cur = 0;
		for (int i = 29; i >= 0; i--) {
			int &p = ptr[cur][getbit(x, i)];
			if (!p) 
				p = ++node;
			cur = p;
			pos[cur].insert(id);
		}
	}
 
	int getmax(int x, int l, int r) {
		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;
				auto it = pos[p].lower_bound(l);
				if (it == pos[p].end() || *it > r)
					continue;
				found = true;
				cur = p;
				res |= (val << i);
				break;
			}	
			if (!found)
				return -1;
		}
		return res;
	}
 
};
 
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 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);

	trie tree(N);

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

	}
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 349544 KB Output is correct
2 Correct 363 ms 349636 KB Output is correct
3 Correct 378 ms 349652 KB Output is correct
4 Correct 383 ms 349688 KB Output is correct
5 Correct 366 ms 349504 KB Output is correct
6 Correct 367 ms 349508 KB Output is correct
7 Correct 372 ms 349616 KB Output is correct
8 Correct 378 ms 349652 KB Output is correct
9 Correct 429 ms 349464 KB Output is correct
10 Correct 393 ms 349600 KB Output is correct
11 Correct 370 ms 349628 KB Output is correct
12 Correct 381 ms 349744 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 349544 KB Output is correct
2 Correct 363 ms 349636 KB Output is correct
3 Correct 378 ms 349652 KB Output is correct
4 Correct 383 ms 349688 KB Output is correct
5 Correct 366 ms 349504 KB Output is correct
6 Correct 367 ms 349508 KB Output is correct
7 Correct 372 ms 349616 KB Output is correct
8 Correct 378 ms 349652 KB Output is correct
9 Correct 429 ms 349464 KB Output is correct
10 Correct 393 ms 349600 KB Output is correct
11 Correct 370 ms 349628 KB Output is correct
12 Correct 381 ms 349744 KB Output is correct
13 Correct 403 ms 350184 KB Output is correct
14 Correct 366 ms 350704 KB Output is correct
15 Correct 377 ms 351300 KB Output is correct
16 Correct 373 ms 351768 KB Output is correct
17 Correct 380 ms 350048 KB Output is correct
18 Correct 374 ms 350680 KB Output is correct
19 Correct 366 ms 351172 KB Output is correct
20 Correct 434 ms 351772 KB Output is correct
21 Correct 387 ms 350072 KB Output is correct
22 Correct 403 ms 350600 KB Output is correct
23 Correct 371 ms 351232 KB Output is correct
24 Correct 376 ms 351684 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 920 ms 524288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 349544 KB Output is correct
2 Correct 363 ms 349636 KB Output is correct
3 Correct 378 ms 349652 KB Output is correct
4 Correct 383 ms 349688 KB Output is correct
5 Correct 366 ms 349504 KB Output is correct
6 Correct 367 ms 349508 KB Output is correct
7 Correct 372 ms 349616 KB Output is correct
8 Correct 378 ms 349652 KB Output is correct
9 Correct 429 ms 349464 KB Output is correct
10 Correct 393 ms 349600 KB Output is correct
11 Correct 370 ms 349628 KB Output is correct
12 Correct 381 ms 349744 KB Output is correct
13 Correct 403 ms 350184 KB Output is correct
14 Correct 366 ms 350704 KB Output is correct
15 Correct 377 ms 351300 KB Output is correct
16 Correct 373 ms 351768 KB Output is correct
17 Correct 380 ms 350048 KB Output is correct
18 Correct 374 ms 350680 KB Output is correct
19 Correct 366 ms 351172 KB Output is correct
20 Correct 434 ms 351772 KB Output is correct
21 Correct 387 ms 350072 KB Output is correct
22 Correct 403 ms 350600 KB Output is correct
23 Correct 371 ms 351232 KB Output is correct
24 Correct 376 ms 351684 KB Output is correct
25 Runtime error 920 ms 524288 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -