제출 #1196656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196656		APROHACK	Klasika (COCI20_klasika)	C++20	33 / 110	5053 ms	30740 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;


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);
	}
}

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);
	}

	distances.clear();
	find_subtree(u, 0);
	for(auto &query : queries_node[u]){
		ans_query[query.id] = 0;
		for(int i = 0 ; i < distances.size() ; ++ i){
			if(distances[i].ss > query.last_node)continue;
			ans_query[query.id] = max(ans_query[query.id], query.XORab ^ distances[i].ff);
		}
	}
}




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: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44