oj.uz

Submission #846662

# Submission time Handle Problem Language Result Execution time Memory
846662 2023-09-08T08:31:51 Z Onur_Ilgaz Klasika (COCI20_klasika) C++17
0 / 110
 749 ms 147284 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 par[N], 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 st, int nd) { // euler tour nowleri
		return nodes.lower_bound(st) != (nodes.upper_bound(nd));
	}
};

void add(Node* node, int val, int nodeNo, int depth = (1<<30)) { // nodeNo query aralığı
	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);
}

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

	if(node->next[wantBit]->doWeHave(st, nd)) {
		// cout<<ret<<", wantedandhad\n";
		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") {
			par[now] = a;
			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 2 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 2 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 749 ms 147284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

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