oj.uz

Submission #671263

# Submission time Handle Problem Language Result Execution time Memory
671263 2022-12-12T14:53:17 Z Nimbostratus Klasika (COCI20_klasika) C++17
0 / 110
 807 ms 180004 KB 
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using lint = long long;
const int maxn = 2e5 + 5;
const int inf = 1e9 + 5;
const int mod = 1e9 + 7;

struct node {
	int ch[2] = {0, 0};
	set<pair<int, int>> s;
};

int n, q;
int tin[maxn], tout[maxn];
vector<int> adj[maxn];
int val[maxn];
array<int, 3> qry[maxn];
vector<node> trie;

void dfs(int u, int p) {
	static int timer = 0;
	tin[u] = ++timer;
	for(int v : adj[u]) {
		if(v == p)
			continue;
		dfs(v, u);
	}
	tout[u] = ++timer;
}

//k at most 31
void add(int idx, int k, int num, int u) {
	trie[idx].s.insert({tin[u], tout[u]});
	if(k == 0)
		return;
	if(!trie[idx].ch[0]) {
		trie.push_back(node());
		trie[idx].ch[0] = trie.size() - 1;
	}
	if(!trie[idx].ch[1]) {
		trie.push_back(node());
		trie[idx].ch[1] = trie.size() - 1;
	}
	int newidx = trie[idx].ch[!!(num & (1 << (k - 1)))];
	add(newidx, k - 1, num, u);
}

//k at most 31
int query(int idx, int k, int num, int u) {
	if(k == 0)
		return 0;
	if(!trie[idx].ch[0]) {
		trie.push_back(node());
		trie[idx].ch[0] = trie.size() - 1;
	}
	if(!trie[idx].ch[1]) {
		trie.push_back(node());
		trie[idx].ch[1] = trie.size() - 1;
	}
	int curbit = !!(num & (1 << (k - 1)));
	auto& s = trie[trie[idx].ch[1 ^ curbit]].s;
	auto it = s.lower_bound({tin[u], tout[u]});
	if(it == s.end() || it->first > tout[u])
		return query(trie[idx].ch[curbit], k - 1, num, u);
	return (1 << (k - 1)) | query(trie[idx].ch[1 ^ curbit], k - 1, num, u); 
}


signed main() {
	#ifdef Local
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> q;
	n = 1;
	for(int i = 1; i <= q; i++) {
		int x, y;
		string op;
		cin >> op >> x >> y;
		if(op == "Add") {
			qry[i][0] = 1;
			n++;
			qry[i][1] = x;
			qry[i][2] = n;
			adj[x].push_back(n);
			val[n] = val[x] ^ y;
		}
		else {
			qry[i][0] = 2;
			qry[i][1] = x;
			qry[i][2] = y;
		}
	}
	dfs(1, 0);
	trie.push_back(node());
	for(int i = 1; i <= q; i++) {
		if(qry[i][0] == 1)
			add(0, 31, val[qry[i][2]], qry[i][2]);
		else
			cout << query(0, 31, val[qry[i][1]], qry[i][2]) << endl;
	}
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5360 KB Output is correct
2 Incorrect 3 ms 5424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5360 KB Output is correct
2 Incorrect 3 ms 5424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 807 ms 180004 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 5360 KB Output is correct
2 Incorrect 3 ms 5424 KB Output isn't correct
3 Halted 0 ms 0 KB -