Need help with XORMIN?

help
, ,
1

I want to know why my solution to xormin using trie and segment-tree is not get accepted ?

2

Because number of queries are too many and O(N*log(n)*20 + Q*log(n)*20) won’t pass in 2 secs.
Try reducing it to O(N*log(n)*20 + Q*20)

2 Likes
3

so what should be the approach ?

4

Persistent trie
different root for each node on given tree…
You don’t need segment tree…

6

After thinking a lot, I exactly thought of a solution with persistent tries. But it kept giving me RE.
Then I thought to try a brute force but then it also gave me RE and then WA. I still could not find out the mistake in my brute force solution. I request you to look into it once.
https://www.codechef.com/viewsolution/24019892
Thanks in advance…

7

@sassy_cat

Here is your solution edited and AC with 10 points.

Problem was you assumed the edges in input to be from parent to child always… which is not the case. As the graph is undirected.
I have added 5 lines and one function.
Check and feel free to ask queries.

1 Like