usaco-guide
usaco-guide copied to clipboard
cpinitiative
Contact Form Submission - Suggestion (Centroid Decomposition)
Someone submitted the contact form!
URL: https://usaco.guide/problems/cses-2081-fixed-length-paths-ii/solution Module: Centroid Decomposition Topic: Suggestion Message: The internal solution for CSES - Fixed-Length Paths II (the centroid decomp one), TLEs on cses judge
you're right. perhaps the judges have gotten slower or tests have been added to this problem. I would suggest removing the binary indexed tree from the solution to remove a log factor.
how is that possible, can you please explain (if there is a solution other than small-to-large merging using cd)
I'm not sure what you mean by small-to-large merging using cd. The centroid decomposition solution in the module doesn't use small-to-large merging.
The idea for speeding up the centroid decomposition solution is to use that the indices of each update / query change only by one between consecutive queries or updates. So each of them can be done in O(1) instead of O(log N) time.
Alternatively, you can do all updates in O(1), then do prefix sums, then do all queries in O(1).