I asked this from the best coder of my college and he was totally clueless and so am I. This is the question: https://mirror.codeforces.com/problemset/problem/4/A. My approach is to use a segment tree of balanced binary search trees and then apply heavy-light decomposition and binary lifting but it gives wrong answer on test 1.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
Same doubt. woofwoof321
Please sir, help me!
I have also used similar approach and solved the problem. Actually you are doing it wrong you have to just create the equivalent binary tree and apply centroid decomposition on that tree. Final answer will be stored in a sparse table. I hope it helps. woofwoof321
nishantwrp I tried your approach but got TLE on test 69. Your approach is quite complicated compared to mine but I can guarantee you that my code didn't have any bugs. I think the time limit in this question is too strict. Can you please give me some tips on how to squeeze this solution in the time limit?
Oh I see. I had problems with that as well, got TLE a few times. I think you forgot to make your centroid decomposition persistent. Also make sure to use a lot of bitsets for speed boost. It will barely fit in the time limit. Happy to help. woofwoof321
Wow! Thank you so much for your help nishantwrp!I finally got this question accepted!! Using bitsets certainly helped a lot. I am flabbergasted I couldn't think of it on my own.
Thank you for such a brilliant solution. I am glad that there are coders like you to help us.
.
Thanks nishantwrp,this blog was really very helpful.when i first saw the question i barely could think of any approach,even after reading the tuitorial i was unable to understand the solution but your approach was very easy to understand..
nishantwrp Wow! Your approach is much simpler and way more intuitive than the one given in the editorial. Thanks for sharing such an awesome approach with the rest of the Codeforces community!
woofwoof321 , Jimmy Neutron, boy genius
Edit: sorry if I have offended anyone, I was just trying to meme it up.
I guess the OP took offense and worked hard and became orange just to get back at you lol xD
Yes, congrats MetB!
what is this? a bullshit blog get 22 upvote?
I did the following: maintain a cartesian treap for each node in the graph and compute the number of hamiltonian paths after compressing the SCC's. This is a standard technique taught in my hometown of Area 69.