LCC '18 Contest 5 S5 - Recipe

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem types

You are cooking a large, seven-layer cake for an upcoming party. You have very little time left, so you would like to complete the cake in as little time as possible.

The recipe for the cake requires \(N\) different ingredients, numbered from 1 to \(N\). The cake itself is considered an ingredient with index \(N+1\). Each ingredient takes an hour to prepare, however some ingredients require other ingredients to be prepared first. For example, a "frosting" ingredient might require the "sugar", "butter", and "milk" ingredients to be prepared first. Each ingredient (excluding the cake) is used as a component of exactly one other ingredient.

You can prepare at most \(M\) ingredients at a time. Given these constraints, what is the minimum amount of time required for you to prepare the cake?

Input Specification

The first line of input contains an integer \(N\) \((1 \le N, M \le 100,000)\), the number of ingredients and the number of ingredients you can prepare at the same time. The next line contains \(N\) integers \(A_i\) \((i < A_i \le N + 1)\), stating that ingredient \(i\) is required for ingredient \(A_i\).

For 40 of 100 points, \(N \le 20\).

Output Specification

Output the minimum number of hours required to prepare the cake.

Sample Input 1

2 1
3 3

Sample Output 1


Sample Input 2

4 2
3 3 5 5

Sample Output 2



There are no comments at the moment.