oj.uz

Submission #847849

# Submission time Handle Problem Language Result Execution time Memory
847849 2023-09-10T15:22:12 Z vjudge1 Klasika (COCI20_klasika) C++17
0 / 110
 550 ms 148944 KB 
#include <bits/stdc++.h>
#include<unistd.h> 
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 200005
using namespace std;
int in[N], out[N], xr[N];
vector <pair<bool, pair<int, int> > > queries;
vector <vector<int> > adj(N);
int now = 2, tine = 0, idtime = 0;

void dfs(int node) {
	in[node] = tine;
	tine++;
	for(auto it:adj[node]) {
		dfs(it);
	}
	out[node] = tine - 1;
}

struct Node {
	Node* next[2] = {NULL, NULL};
	int id;
	set <int> nodes;
	bool doWeHave(int left, int right) {
	    // Find the first element that is not less than 'left'
	    auto lower = nodes.lower_bound(left);

	    // If 'lower' is not greater than 'right', there is an integer in the range
	    return lower != nodes.end() && *lower <= right;
	}
};

void add(Node* node, int val, int nodeNo, int depth = (1<<30)) { 
	int st = in[nodeNo];
	node->nodes.insert(st);
	bool bit = (val & depth);
	if(depth == 0) return;
	if(node->next[bit] == NULL) {
		node->next[bit] = new Node();
		node->next[bit]->id = idtime;
		idtime++;
	}
	add(node->next[bit], val, nodeNo, depth / 2);
}

int query(Node* node, int want, int nodeNo, int depth = (1<<30), int ret = 0) {
	if(depth == 0) return ret;
	int st = in[nodeNo], nd = out[nodeNo];
	bool wantBit = !(want & depth);
	if(node->next[wantBit] == NULL) {
		node->next[wantBit] = new Node();
		node->next[wantBit]->id = idtime;
		idtime++;
	}

	if(node->next[wantBit]->doWeHave(st, nd)) {
		return query(node->next[wantBit], want, nodeNo, depth / 2, ret + (depth * wantBit));
	}
	if(node->next[!wantBit] == NULL) {
		node->next[!wantBit] = new Node();
		node->next[!wantBit]->id = idtime;
		idtime++;
	}
	return query(node->next[!wantBit], want, nodeNo, depth / 2, ret + (depth * (!wantBit)));
}

int32_t main(){
	fast
	int q;
	cin>>q;
	while(q--) {
		string s;
		int a, b;
		cin>>s>>a>>b;
		if(s == "Add") {
			adj[a].push_back(now);
			now++;
			queries.push_back({1, {a, b}});
		}
		else {
			queries.push_back({0, {a, b}});
		}
	}
	dfs(1);
	Node* root = new Node();
	root->id = -1;
	now = 2;
	for(auto it:queries) {
		bool type = it.first;
		int a = it.second.first, b = it.second.second;
		if(type) {
			xr[now] = xr[a] ^ b;
			add(root, xr[now], now);
			now++;
		}
		else {
			cout<<(xr[a] ^ query(root, xr[a], b))<<"\n";
		}
	}
}

Subtask #1
0 / 11.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 550 ms 148944 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 9308 KB Output is correct
2 Incorrect 2 ms 9564 KB Output isn't correct
3 Halted 0 ms 0 KB -