oj.uz

Submission #291243

# Submission time Handle Problem Language Result Execution time Memory
291243 2020-09-04T23:38:29 Z penguinhacker Klasika (COCI20_klasika) C++17
33 / 110
 669 ms 21228 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int MAXDIG=30;
struct Node {
	int cnt=0;
	int nxt[2];
	Node() {nxt[0]=nxt[1]=-1;}
};
struct Trie {
	vector<Node> trie;
	Trie() {trie.emplace_back();}
	void reset() {trie.clear(); trie.emplace_back();}
	void add(int x) {
		int cur=0;
		++trie[0].cnt;
		for (int i=MAXDIG; ~i; --i) {
			int c=(x>>i)&1;
			if (trie[cur].nxt[c]==-1) {
				trie[cur].nxt[c]=trie.size();
				trie.emplace_back();
			}
			cur=trie[cur].nxt[c];
			++trie[cur].cnt;
		}
	}

	int qry(int x) { //best xor in trie 
		int cur=0;
		int res=0;
		for (int i=MAXDIG; ~i; --i) {
			int c=(x>>i)&1;
			if (trie[cur].nxt[c^1]!=-1&&trie[trie[cur].nxt[c^1]].cnt>0) {
				res+=(1<<i);
				cur=trie[cur].nxt[c^1];
			}
			else {
				cur=trie[cur].nxt[c];
			}
		}
		return res;
	}
} trie;

const int mxN=2e5;
int n=1, val[mxN];
vector<int> adj[mxN];

int dfs(int u, int x) {
	int MX=x^val[u];
	for (int v: adj[u]) {
		MX=max(MX, dfs(v, x));
	}
	return MX;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int q; cin >> q;
	while(q--) {
		string type; cin >> type;
		int a, b; cin >> a >> b;
		if (type=="Add") {
			--a;
			val[n]=val[a]^b;
			adj[a].push_back(n);
			trie.add(val[n]);
			++n;
		}
		if (type=="Query") {
			--a, --b;
			int ans=q<=2000?dfs(b, val[a]):trie.qry(val[a]);
			cout << ans << "\n";
		}
	}
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 3 ms 5120 KB Output is correct
4 Correct 3 ms 5120 KB Output is correct
5 Correct 3 ms 5120 KB Output is correct
6 Correct 3 ms 5120 KB Output is correct
7 Correct 3 ms 5120 KB Output is correct
8 Correct 3 ms 5120 KB Output is correct
9 Correct 3 ms 5120 KB Output is correct
10 Correct 3 ms 5120 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct
12 Correct 4 ms 5120 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 3 ms 5120 KB Output is correct
4 Correct 3 ms 5120 KB Output is correct
5 Correct 3 ms 5120 KB Output is correct
6 Correct 3 ms 5120 KB Output is correct
7 Correct 3 ms 5120 KB Output is correct
8 Correct 3 ms 5120 KB Output is correct
9 Correct 3 ms 5120 KB Output is correct
10 Correct 3 ms 5120 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct
12 Correct 4 ms 5120 KB Output is correct
13 Correct 6 ms 5392 KB Output is correct
14 Correct 6 ms 5580 KB Output is correct
15 Correct 7 ms 5580 KB Output is correct
16 Correct 7 ms 6024 KB Output is correct
17 Correct 5 ms 5376 KB Output is correct
18 Correct 5 ms 5572 KB Output is correct
19 Correct 5 ms 5576 KB Output is correct
20 Correct 5 ms 5576 KB Output is correct
21 Correct 5 ms 5376 KB Output is correct
22 Correct 6 ms 5576 KB Output is correct
23 Correct 5 ms 5576 KB Output is correct
24 Correct 5 ms 5636 KB Output is correct

Subtask #3
0 / 33.0

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

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 3 ms 5120 KB Output is correct
4 Correct 3 ms 5120 KB Output is correct
5 Correct 3 ms 5120 KB Output is correct
6 Correct 3 ms 5120 KB Output is correct
7 Correct 3 ms 5120 KB Output is correct
8 Correct 3 ms 5120 KB Output is correct
9 Correct 3 ms 5120 KB Output is correct
10 Correct 3 ms 5120 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct
12 Correct 4 ms 5120 KB Output is correct
13 Correct 6 ms 5392 KB Output is correct
14 Correct 6 ms 5580 KB Output is correct
15 Correct 7 ms 5580 KB Output is correct
16 Correct 7 ms 6024 KB Output is correct
17 Correct 5 ms 5376 KB Output is correct
18 Correct 5 ms 5572 KB Output is correct
19 Correct 5 ms 5576 KB Output is correct
20 Correct 5 ms 5576 KB Output is correct
21 Correct 5 ms 5376 KB Output is correct
22 Correct 6 ms 5576 KB Output is correct
23 Correct 5 ms 5576 KB Output is correct
24 Correct 5 ms 5636 KB Output is correct
25 Incorrect 669 ms 21228 KB Output isn't correct
26 Halted 0 ms 0 KB -