Sonic And Notifications
All submissions for this problem are available.
Sonic has been made the student representative of his college for INNOVISION, 2K17. Each student in the college reports to a unique senior student, except the student representative (that is Sonic). This hierarchy can be modelled as a tree, rooted at the student representative. Nodes 'v' having parent node 'u' means that 'u' is the senior student to which node 'v' reports. Also node 'v' is a junior to node 'u'.
In case of any notifications regarding INNOVISION, 2K17, Sonic first notifies his juniors one at a time. The juniors in turn notify their juniors one at a time. This continues until every student in the college has been notified. We can divide this process into times. In one time, a student who has learnt of the notification can notify to one of his juniors. The total time it takes for everyone to get notified depends on the sequence in which a senior calls their juniors. Help Sonic determine the minimum total time needed to notify all the students.
- First line contains 'n' denoting the number of students.
- 'n-1' space separated integers follow. (i)th integer denotes that it is the parent of (i+1)th node.
- The minimum total time required.
Should contain all the constraints on the input data that you may have. Format it like:
- 1 <= n <= 100000
- 1 <= parent[i] <= n
- parent[i] != i
Input: 4 1 2 1 Output: 2
Explanation: The tree can be considered as: 1 -> 2 2 -> 3 1 -> 4 Consider first situation:- First time: 1 notifies to 2. Second time: 1 notifies to 4 and 2 notifies to 3. Consider another situation:- First time: 1 notifies to 4. Second time: 1 notifies to 2. Third time: 2 notifies to 3. Therefore first situation is better as it takes 2 units of total time.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions