TLE in Nutella Path Unit when using Binary Lifting

CodeChef-DSA-learners
1

solution , this is my solution for the question Nutella Path Unit .
The link to the question is ENOC1 .
I am not able to understand whats going wrong as i feel the approach should be quick enough. Please suggest some changes .

2

problem is in this line

void dfs(ll ind,vector<ll> x[],vector<ll> y,ll z,ll par,ll lev){

you are copying vector<ll> y everytime.

2 Likes
3

thanks a lot , changing that part worked

1 Like
4

Can you please explain your approach?

1 Like
5

I think mine is similar, so I’ll explain it.
dp_v is the answer for the path from 1 to v. Obviously, dp_v = dp_u \oplus a_v.
You want the answer for the path from u to v, so let’s consider the second query in the sample test case.
dp_4 = a_1 \oplus a_2 \oplus a_4 and dp_5 = a_1 \oplus a_2 \oplus a_5.
dp_4 \oplus dp_5 = a_4 \oplus a_5 (notice that the duplicates get cancelled). Now, you have the XORs of all nodes only in 4's and 5's path (from 1). XOR this with a_{\text{lca}(4, \ 5)} because \text{lca}(4, \ 5) is in the path from 4 to 5, but is also a duplicate value.
So the answer is dp_u \oplus dp_v \oplus a_{\text{lca}(u, \ v)} for each query.
Here is my code: code

1 Like