Submission #1196660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196660		APROHACK	Klasika (COCI20_klasika)	C++20	0 / 110	120 ms	40416 KiB

klasika

#include<bits/stdc++.h>

#define ff first
#define ss second 
#define pb push_back
#define sz(a) ((int)((a).size()))
#define inf 1e9
using ll = long long;
using ld = long double;

using namespace std;
const int N = 200005;
struct query{
	int a, b, XORab, id, last_node;
};

vector<query>queries;

const int MX = 200000 * 20;

int go[MX][2];
int first[MX];
int lazy[MX];

struct TRIE{
	private: 
		int nxt;

		int generate_node(){
			go[nxt][0] = -1;
			go[nxt][1] = -1;
			first[nxt] = INT_MAX;
			lazy[nxt] = 0;
			return nxt ++ ;
		}

		void propagate(int u, int bit){
			if(lazy[u] == 0)return ;
			if((lazy[u] >> bit) & 1){
				swap(go[u][0], go[u][1]);
			}
			if(go[u][0] != -1){
				lazy[go[u][0]] ^= lazy[u];
			}
			if(go[u][1] != -1){
				lazy[go[u][1]] ^= lazy[u];
			}
			lazy[u] = 0;
		}

		

		int find_maximum(int u, int x, int bit, int &last_node){
			if(bit >= 0){
				propagate(u, bit);
			}
			
			if(bit == -1){
				return 0;
			}
			if((1 << bit) & x){
				// wants 0
				if(go[u][0] != -1 && first[go[u][0]] <= last_node){
					// cout << "move " << 0 << endl;
					return (1 << bit) + find_maximum(go[u][0], x, bit - 1, last_node);
				}else{
					// cout << "move " << 1 << endl;
					return find_maximum(go[u][0], x, bit - 1, last_node);;
				}
			}else{
				// wants 1
				if(go[u][1] != -1 && first[go[u][1]] <= last_node){
					// cout << "move " << 1 << endl;
					return (1 << bit) + find_maximum(go[u][1], x, bit - 1, last_node);
				}else{
					// cout << "move " << 0 << endl;
					return find_maximum(go[u][0], x, bit - 1, last_node);
				}
			}
		}

		void insert_value(int u, int &x, int bit, int &time){
			if(bit >= 0){
				propagate(u, bit);
			}
			first[u] = min(first[u], time);

			if(bit == -1){
		
				return ;
			}

			if((1 << bit) & x){
				if(go[u][1] == -1)go[u][1] = generate_node();
				insert_value(go[u][1], x, bit - 1, time);
			}else{
				if(go[u][0] == -1)go[u][0] = generate_node();
				insert_value(go[u][0], x, bit - 1, time);
			}
		}

	public:

		void reinit (){
			nxt = 1;
			go[0][0] = - 1;
			go[0][1] = -1;
			first[0] = INT_MAX;
			lazy[0] = 0;
			#ifdef LOCAL
			// cout << "reinit " << endl;
			#endif
		}

		int find_maximum(int x, int last_node){
			return find_maximum(0, x, 30, last_node);
		}

		void insert_value(int x, int time){
			insert_value(0, x, 30, time);
			#ifdef LOCAL
			// cout << x << " " << time << " inserted " << endl;
			#endif
		}

		TRIE(){

		}



};





vector<pair<int, int> >adj[N];
vector<query>queries_node[N];
int parent[N];
int parent_weight[N];

int sparse[N][20];
int XOR[N][20];
int depth[N];
int sz[N];
int ans_query[N];

int last_node;

struct LCA{
	
	
	LCA(){
		for(int i = 1 ; i <= last_node ; ++ i){
			sparse[i][0] = parent[i];
			XOR[i][0] = parent_weight[i];
		}

		for(int b = 1 ; b < 20 ; ++ b){
			for(int i = 1 ; i <= last_node ; ++ i){
				sparse[i][b] = sparse[sparse[i][b - 1]][b - 1];
				XOR[i][b] = XOR[sparse[i][b - 1]][b - 1] ^ XOR[i][b - 1];
			}
		}
	}

	int find_xor(int a, int b){
		if(a == b)return 0;

		if(depth[a] < depth[b])swap(a, b);
		// A is deeper

		int distancia = depth[a] - depth[b];
		int ans = 0;

		for(int bit = 19 ; bit >= 0 ; -- bit){
			if((1 << bit) & distancia){
				ans ^= XOR[a][bit];
				a = sparse[a][bit];
			}
		}

		// A is at the same depth as B

		if(a == b)return ans;

		for(int bit = 19 ; bit >= 0 ; -- bit){
			if(sparse[a][bit] == sparse[b][bit])continue;
			ans ^= XOR[a][bit];
			ans ^= XOR[b][bit];
			a = sparse[a][bit];
			b = sparse[b][bit];
		}

		// Subir uno mas
		ans ^= XOR[a][0];
		ans ^= XOR[b][0];
		return ans;
	}
};

void dfs_construct(int u, int d){
	sz[u] = 1;
	depth[u] = d;
	for(auto &c : adj[u]){
		dfs_construct(c.ff, d + 1);
		sz[u] += sz[c.ff];
	}
}

vector<pair<int, int>>distances;

void find_subtree(int u, int x){
	distances.push_back({x, u});
	for(auto &c : adj[u]){
		int v = c.ff;
		int w = c.ss;
		find_subtree(v, x ^ w);
	}
}

TRIE trie;

void dfs_solve(int u, int is_big){

	for(auto &c : adj[u]){
		int v = c.ff;
		int w = c.ss;
		dfs_solve(v, false);
	}

	if(queries_node[u].empty())return ;

	distances.clear();
	find_subtree(u, 0);
	trie.reinit();

	for(int i = 0 ; i < distances.size() ; ++ i){
		trie.insert_value(distances[i].ff, distances[i].ss);
	}

	for(auto &query : queries_node[u]){
		ans_query[query.id] = trie.find_maximum(query.XORab, query.last_node);
	}
}




int main(){
    #ifdef LOCAL
		//freopen("in","r", stdin);
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0);

	int q;
	cin >> q;
	last_node = 1;
	parent[1] = 1;
	for(int i = 0 ; i < q ; ++ i){
		string type ;
		cin >> type;
		if(type == "Add"){
			int x, y;
			cin >> x >> y;
			parent[ ++ last_node] = x;
			parent_weight[last_node] = y;
			adj[x].push_back({last_node , y});
		}else{
			int a, b;
			cin >> a >> b;
			queries.push_back({a, b, -1, i, last_node});
		}
	}

	dfs_construct(1, 0);

	LCA lca;


	for(int i = 0 ; i < queries.size() ; ++ i){
		queries[i].XORab = lca.find_xor(queries[i].a, queries[i].b);
		queries_node[queries[i].b].pb(queries[i]);
	}

	dfs_solve(1, 0);

	for(int i = 0 ; i < queries.size() ; ++ i){
		cout << ans_query[queries[i].id] << "\n";
	}

	
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44