Solve FCTREE without MO's Algo

ra_jatt · April 13, 2020, 8:21pm

I tried to solve FCTREE without MO’s Algo. I calculated LCA using the sparse table and then moved along the table and calculated number of divisors using sieve method. On submission
I got runtime error for all subtasks. If someone can help or suggest some possible errors. Attached below is my code:
https://www.codechef.com/viewsolution/31843262

sunny_52525 · April 13, 2020, 8:24pm

Product will give integer overflow.
you need to do prime factorisation of each node individually.

sunny_52525 · April 13, 2020, 8:25pm

sieve you used also gave me RE.
Probably its not made for >10^5

ra_jatt · April 13, 2020, 8:37pm

Yeah then that might be the right reason. Thanks

sunny_52525 · April 13, 2020, 8:41pm

try this one. this atleast gave me partial

imrajatmehta · April 13, 2020, 8:41pm

same happened to me

imrajatmehta · April 13, 2020, 8:43pm

i used sieve also used hashmap but still getting RE
i think RE is coming because of memory limit exceed because of sparse table

sunny_52525 · April 13, 2020, 8:46pm

No actually I was using different method for factorisation. It was giving TLE . Then changed it to the sieve used in OP then it started giving me RE. Segmentation fault.
Then I again changed the factorisation method (see my link) then it ran fine for subtask 1…
I didn’t change sparse table during this so I think it wasn’t sparse fault.

ra_jatt · April 14, 2020, 6:37am

Yeah!!
Same happened with mine. Though i didnot end up getting AC in any subtask.