bluemmb's blog

Queries on tree — Codechef
By bluemmb, 9 years ago, In English

Hello .

I tried to solve this problem but my submission got SIGSEGV for one of tests and I can't find reason!

I used huge random and clever inputs many times for my solution and test them with online judge compile options but it pass all of them without problem.

Can someone help me ?

Little Details : I wrote comment for codes and I used ...

for solving problem >> Dfs Order + Segment Tree , actually I found path from root to all nodes and updated them with help of segment tree on range that are under related node in dfs order.

So Answer is : ans(u) + ans(v) — 2*ans( lca(u,v) );

for finding LCA >> EulerTour + SparseTable

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by bluemmb (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Stack overflow can be a reason (usually it's 8 MB by default on Linux). I was unable to quickly found an information about stack limit on CodeChef, though. Maybe it's equal to memory limit, like on adequate judges.

Btw, it was a real problem on TopCoder until they raised stack limit several years ago from default 8 MB to somewhat customizable.

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

As far as I remember, Codechef's stack size is very very low.

→ Reply