Seferovic's blog

Debug Help Needed: Centroid Decomposition Weird TLE
By Seferovic, history, 9 months ago, In English

Hello CodeForces, today I tried solving the problem from a recent contest: 1923E - Count Paths

My Solution:

Solution

If you see any problems with the code, please let me know as I can't see the problem. If you don't understand a part of the code, please ask and I will clarify.

Submission: 255437477

UPD: The runtime takes more than 30 seconds! So I guess the runtime is O(N^2) somehow.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

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

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish I could help

→ Reply
»
94 minutes ago, # |
  Vote: I like it +2 Vote: I do not like it

Your centroid finding code has a bug where it compares the size of its child with the parent, but it should check with the size of the current root.

→ Reply