All submissions for this problem are available.
There are n tasks to be completed. Each task ti has an individual time requirement of ci minutes and is dependent on a number of other tasks. It requires at least ri of the tasks that task ti depends on, to be completed before ti can start. Also, if task ti is dependent on tj, then ti can only start a minute after the completion of tj. Independent tasks can be executed simultaneously.
We need to find the minimum time in which all the tasks can be completed, provided the dependencies are satisfied.
For each test case, the first line of input specifies the number of tasks, n (numbered from 0 to n-1).
The next n lines specify the time requirement and dependency requirement in the following format:
The next line specifies the number of dependencies, p.
The next p lines specify the dependencies in ti
max (ri) < 50
max (ci) <= 100000
The minimum time required to complete all tasks (in minutes), one test case per line.
Input: 1 4 1 2 2 0 4 0 2 0 3 0 1 0 2 0 3 Output: 4
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 6.3, CPP14, GO, NODEJS|
Fetching successful submissions
If you are still having problems, see a sample solution here.