Editorial for Bonus Project

Prerequisites: Breadth First Search / Depth First Search

Explanation: At first lets see two observation -

  1. Company structure is a tree structure. The head of the company (employee number 11) is the root of the tree.

  2. For each query you don’t have to print answer online. So after final query, one bfs or dfs call is enough for getting final account balance for all employees.

So for each query sums up the amount YY in node XX (team leader) and also sums up the amount YY in initial account of node XX (as XX will get 2Y2Y bonus).

Finally run a bfs or dfs from Node 11 (head of the company). Using push down method to update each child account balance. Then calculate final account balance for each node XX by adding the initial balance with it.

One can also solve it using tree flattening and segment tree.

Time Complexity: for bfs or dfs, O(n)O(n)

Setter’s Solution


    85% Solution Ratio

    Sharif_11Earliest, 3M ago

    Minus_XFastest, 0.3s

    Uosmoy383Lightest, 54 MB

    Zobayer_AbedinShortest, 816B

    Toph uses cookies. By continuing you agree to our Cookie Policy.