oj.uz

Submission #847910

# Submission time Handle Problem Language Result Execution time Memory
847910 2023-09-10T19:28:24 Z vjudge1 Klasika (COCI20_klasika) C++17
110 / 110
 3078 ms 492016 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#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 = 30;
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 2 ms 5468 KB Output is correct
2 Correct 2 ms 5468 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 3 ms 5784 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 2 ms 5724 KB Output is correct
8 Correct 2 ms 5784 KB Output is correct
9 Correct 2 ms 5464 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Correct 2 ms 5724 KB Output is correct
12 Correct 3 ms 5676 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5468 KB Output is correct
2 Correct 2 ms 5468 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 3 ms 5784 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 2 ms 5724 KB Output is correct
8 Correct 2 ms 5784 KB Output is correct
9 Correct 2 ms 5464 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Correct 2 ms 5724 KB Output is correct
12 Correct 3 ms 5676 KB Output is correct
13 Correct 5 ms 7700 KB Output is correct
14 Correct 9 ms 11280 KB Output is correct
15 Correct 9 ms 11024 KB Output is correct
16 Correct 10 ms 11020 KB Output is correct
17 Correct 5 ms 7700 KB Output is correct
18 Correct 8 ms 10000 KB Output is correct
19 Correct 9 ms 10012 KB Output is correct
20 Correct 10 ms 11280 KB Output is correct
21 Correct 6 ms 7696 KB Output is correct
22 Correct 8 ms 10000 KB Output is correct
23 Correct 9 ms 11164 KB Output is correct
24 Correct 10 ms 11280 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 193032 KB Output is correct
2 Correct 1254 ms 370092 KB Output is correct
3 Correct 1856 ms 381676 KB Output is correct
4 Correct 2301 ms 490232 KB Output is correct
5 Correct 784 ms 191616 KB Output is correct
6 Correct 1404 ms 364256 KB Output is correct
7 Correct 2064 ms 380180 KB Output is correct
8 Correct 2685 ms 480356 KB Output is correct
9 Correct 745 ms 188112 KB Output is correct
10 Correct 1291 ms 365908 KB Output is correct
11 Correct 1905 ms 375332 KB Output is correct
12 Correct 2396 ms 482868 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5468 KB Output is correct
2 Correct 2 ms 5468 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 3 ms 5784 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 2 ms 5724 KB Output is correct
8 Correct 2 ms 5784 KB Output is correct
9 Correct 2 ms 5464 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Correct 2 ms 5724 KB Output is correct
12 Correct 3 ms 5676 KB Output is correct
13 Correct 5 ms 7700 KB Output is correct
14 Correct 9 ms 11280 KB Output is correct
15 Correct 9 ms 11024 KB Output is correct
16 Correct 10 ms 11020 KB Output is correct
17 Correct 5 ms 7700 KB Output is correct
18 Correct 8 ms 10000 KB Output is correct
19 Correct 9 ms 10012 KB Output is correct
20 Correct 10 ms 11280 KB Output is correct
21 Correct 6 ms 7696 KB Output is correct
22 Correct 8 ms 10000 KB Output is correct
23 Correct 9 ms 11164 KB Output is correct
24 Correct 10 ms 11280 KB Output is correct
25 Correct 695 ms 193032 KB Output is correct
26 Correct 1254 ms 370092 KB Output is correct
27 Correct 1856 ms 381676 KB Output is correct
28 Correct 2301 ms 490232 KB Output is correct
29 Correct 784 ms 191616 KB Output is correct
30 Correct 1404 ms 364256 KB Output is correct
31 Correct 2064 ms 380180 KB Output is correct
32 Correct 2685 ms 480356 KB Output is correct
33 Correct 745 ms 188112 KB Output is correct
34 Correct 1291 ms 365908 KB Output is correct
35 Correct 1905 ms 375332 KB Output is correct
36 Correct 2396 ms 482868 KB Output is correct
37 Correct 1103 ms 191684 KB Output is correct
38 Correct 1815 ms 368000 KB Output is correct
39 Correct 2185 ms 382200 KB Output is correct
40 Correct 2544 ms 492016 KB Output is correct
41 Correct 1207 ms 185792 KB Output is correct
42 Correct 2011 ms 364608 KB Output is correct
43 Correct 2522 ms 373956 KB Output is correct
44 Correct 3078 ms 479748 KB Output is correct
45 Correct 1385 ms 192484 KB Output is correct
46 Correct 1912 ms 368000 KB Output is correct
47 Correct 2469 ms 374168 KB Output is correct
48 Correct 2874 ms 482956 KB Output is correct