oj.uz

Submission #847908

# Submission time Handle Problem Language Result Execution time Memory
847908 2023-09-10T19:24:47 Z Onur_Ilgaz Klasika (COCI20_klasika) C++17
33 / 110
 1615 ms 524288 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 ----------
	add(0, 1);
	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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 2 ms 7828 KB Output is correct
4 Correct 3 ms 7832 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 3 ms 7832 KB Output is correct
8 Correct 3 ms 7832 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 3 ms 7772 KB Output is correct
11 Correct 3 ms 7832 KB Output is correct
12 Correct 3 ms 7832 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 2 ms 7828 KB Output is correct
4 Correct 3 ms 7832 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 3 ms 7832 KB Output is correct
8 Correct 3 ms 7832 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 3 ms 7772 KB Output is correct
11 Correct 3 ms 7832 KB Output is correct
12 Correct 3 ms 7832 KB Output is correct
13 Correct 7 ms 10004 KB Output is correct
14 Correct 8 ms 12796 KB Output is correct
15 Correct 9 ms 13840 KB Output is correct
16 Correct 12 ms 13836 KB Output is correct
17 Correct 6 ms 10004 KB Output is correct
18 Correct 8 ms 12560 KB Output is correct
19 Correct 9 ms 13156 KB Output is correct
20 Correct 12 ms 13580 KB Output is correct
21 Correct 5 ms 10004 KB Output is correct
22 Correct 9 ms 12560 KB Output is correct
23 Correct 10 ms 12660 KB Output is correct
24 Correct 11 ms 13584 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 216212 KB Output is correct
2 Correct 1060 ms 412844 KB Output is correct
3 Correct 1488 ms 415576 KB Output is correct
4 Runtime error 1615 ms 524288 KB Execution killed with signal 9
5 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 Correct 2 ms 7512 KB Output is correct
3 Correct 2 ms 7828 KB Output is correct
4 Correct 3 ms 7832 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 3 ms 7832 KB Output is correct
8 Correct 3 ms 7832 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 3 ms 7772 KB Output is correct
11 Correct 3 ms 7832 KB Output is correct
12 Correct 3 ms 7832 KB Output is correct
13 Correct 7 ms 10004 KB Output is correct
14 Correct 8 ms 12796 KB Output is correct
15 Correct 9 ms 13840 KB Output is correct
16 Correct 12 ms 13836 KB Output is correct
17 Correct 6 ms 10004 KB Output is correct
18 Correct 8 ms 12560 KB Output is correct
19 Correct 9 ms 13156 KB Output is correct
20 Correct 12 ms 13580 KB Output is correct
21 Correct 5 ms 10004 KB Output is correct
22 Correct 9 ms 12560 KB Output is correct
23 Correct 10 ms 12660 KB Output is correct
24 Correct 11 ms 13584 KB Output is correct
25 Correct 659 ms 216212 KB Output is correct
26 Correct 1060 ms 412844 KB Output is correct
27 Correct 1488 ms 415576 KB Output is correct
28 Runtime error 1615 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -