Блог пользователя Jratos

Автор Jratos, история, 5 часов назад, По-английски

Hi, is there a reason why my submission* got accepted meanwhile my rough estimate for time complexity is O(n^3), because i did a dfs and for every node i calculate a subset sum of each subtree size. Or is this because of weak tc? thanks

*) https://codeforces.me/contest/1856/submission/290385616

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The time complexity will be O($$$n^2$$$). For each node we iterate through it's children and the number of parent-children pairs is n-1. We then calculate the subset sum in O($$$n$$$) leading to O($$$n^2$$$).