oj.uz

Submission #847902

# Submission time Handle Problem Language Result Execution time Memory
847902 2023-09-10T18:59:54 Z Onur_Ilgaz Klasika (COCI20_klasika) C++17
0 / 110
 698 ms 211996 KB 
#include <bits/stdc++.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 tin[N], tout[N], xr[N], edgeVal[N], eulerTime = 1;
vector <vector<int> > adj(N);

const int maxi = 31;
int nodeSize = 0;
vector <int> zero, one;
vector <set<int> > sets;

void newNode() {
	zero.push_back(0);
	one.push_back(0);
	set <int> st;
	sets.push_back(st);
	nodeSize++;
}

void add(int value, int index) {
	int node = 0;
	for(int bit = (1ll << maxi); bit > 0; bit /= 2) { 
		// do recursive shit here

		if(!zero[node]) {
			zero[node] = nodeSize;
			newNode();
			one[node] = nodeSize;
			newNode();
		}

		if(value & bit) {
			node = one[node];
		}
		else {
			node = zero[node];
		}
		sets[node].insert(index);

	}
}

bool areThere(int node, int left, int right) {
	auto it = sets[node].lower_bound(left);

	return (it == sets[node].end()) ? (false) : (*it <= right);
}

int query(int want, int left, int right) {
	int node = 0, ret = 0;
	for(int bit = (1ll << maxi); bit > 0; bit /= 2) { 
		// do recursive shit here
		if(!zero[node]) {
			return ret;
		}

		if(want & bit) { // istediğim 1
			if(areThere(one[node], left, right)) {
				node = one[node];
				ret += bit;
			}
			else {
				node = zero[node];
			}
		}
		else { // istediğim 0
			if(areThere(zero[node], left, right)) {
				node = zero[node];
			}
			else {
				node = one[node];
				ret += bit;
			}
		}
	}
	return ret;
}

void dfs(int node) {
	tin[node] = eulerTime;
	eulerTime++;
	for(auto it:adj[node]) {
		xr[it] = xr[node] ^ edgeVal[it];
		dfs(it);
	}
	tout[node] = eulerTime - 1;
}

int nodeIndex = 2;

int32_t main(){
	fast
	int n;
	cin>>n;
	vector <vector<int> > queries;
	{ // precalculation of euler index
		for(int i = 0; i < n; i++) {
			string type;
			cin>>type;
			if(type == "Add") {
				int parentNode, value;
				cin>>parentNode>>value;
				adj[parentNode].push_back(nodeIndex);

				edgeVal[nodeIndex] = value;

				queries.push_back({1, nodeIndex});
				nodeIndex++;
			}
			else {
				int starting, subTree;
				cin>>starting>>subTree;

				queries.push_back({0, starting, subTree});
			}
		}
		dfs(1);
		nodeIndex--;
		newNode();
	}
	// --------- o ----------
	//! xr kontrol etmedik
	for(auto it:queries) {
		if(it[0]) {
			int nodeIndex = it[1];
			add(xr[nodeIndex], tin[nodeIndex]);
		}
		else {
			int starting = it[1], subTree = it[2];
			int want = ~xr[starting], stbeg = tin[subTree], stend = tout[subTree];
			cout<<(xr[starting] ^ query(want, stbeg, stend))<<"\n";
		}
	}
	
}

Subtask #1
0 / 11.0

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

Subtask #3
0 / 33.0

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