oj.uz

Submission #405228

# Submission time Handle Problem Language Result Execution time Memory
405228 2021-05-16T02:07:51 Z ngpin04 Klasika (COCI20_klasika) C++14
33 / 110
 1713 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 <set <int>> pos;
	vector <vector <int>> ptr;
 
	trie(int n) {
		node = 0;
		ptr.assign(30 * n + 5, vector <int> (2, 0));  
		pos.resize(30 * 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 7 ms 11468 KB Output is correct
2 Correct 8 ms 11596 KB Output is correct
3 Correct 8 ms 11852 KB Output is correct
4 Correct 8 ms 11980 KB Output is correct
5 Correct 7 ms 11428 KB Output is correct
6 Correct 7 ms 11596 KB Output is correct
7 Correct 7 ms 11724 KB Output is correct
8 Correct 9 ms 11980 KB Output is correct
9 Correct 7 ms 11468 KB Output is correct
10 Correct 7 ms 11724 KB Output is correct
11 Correct 8 ms 11852 KB Output is correct
12 Correct 8 ms 11980 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11468 KB Output is correct
2 Correct 8 ms 11596 KB Output is correct
3 Correct 8 ms 11852 KB Output is correct
4 Correct 8 ms 11980 KB Output is correct
5 Correct 7 ms 11428 KB Output is correct
6 Correct 7 ms 11596 KB Output is correct
7 Correct 7 ms 11724 KB Output is correct
8 Correct 9 ms 11980 KB Output is correct
9 Correct 7 ms 11468 KB Output is correct
10 Correct 7 ms 11724 KB Output is correct
11 Correct 8 ms 11852 KB Output is correct
12 Correct 8 ms 11980 KB Output is correct
13 Correct 11 ms 13232 KB Output is correct
14 Correct 14 ms 15076 KB Output is correct
15 Correct 16 ms 16844 KB Output is correct
16 Correct 17 ms 18508 KB Output is correct
17 Correct 11 ms 13084 KB Output is correct
18 Correct 14 ms 14900 KB Output is correct
19 Correct 16 ms 16752 KB Output is correct
20 Correct 18 ms 18488 KB Output is correct
21 Correct 12 ms 13132 KB Output is correct
22 Correct 14 ms 14912 KB Output is correct
23 Correct 16 ms 16716 KB Output is correct
24 Correct 18 ms 18380 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 194936 KB Output is correct
2 Correct 1661 ms 376536 KB Output is correct
3 Runtime error 1713 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 7 ms 11468 KB Output is correct
2 Correct 8 ms 11596 KB Output is correct
3 Correct 8 ms 11852 KB Output is correct
4 Correct 8 ms 11980 KB Output is correct
5 Correct 7 ms 11428 KB Output is correct
6 Correct 7 ms 11596 KB Output is correct
7 Correct 7 ms 11724 KB Output is correct
8 Correct 9 ms 11980 KB Output is correct
9 Correct 7 ms 11468 KB Output is correct
10 Correct 7 ms 11724 KB Output is correct
11 Correct 8 ms 11852 KB Output is correct
12 Correct 8 ms 11980 KB Output is correct
13 Correct 11 ms 13232 KB Output is correct
14 Correct 14 ms 15076 KB Output is correct
15 Correct 16 ms 16844 KB Output is correct
16 Correct 17 ms 18508 KB Output is correct
17 Correct 11 ms 13084 KB Output is correct
18 Correct 14 ms 14900 KB Output is correct
19 Correct 16 ms 16752 KB Output is correct
20 Correct 18 ms 18488 KB Output is correct
21 Correct 12 ms 13132 KB Output is correct
22 Correct 14 ms 14912 KB Output is correct
23 Correct 16 ms 16716 KB Output is correct
24 Correct 18 ms 18380 KB Output is correct
25 Correct 950 ms 194936 KB Output is correct
26 Correct 1661 ms 376536 KB Output is correct
27 Runtime error 1713 ms 524292 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -