Seferoglu's blog

Debug Help Needed: Centroid Decomposition Weird TLE
By Seferoglu, history, 2 years 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

Comments Comments (2)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
16 months ago, hide # |
 
Vote: I like it +14 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