All Tracks Problem

Make n00b_land Great Again!

BIT, Binary search algorithm, Medium, Segment tree, Tree


Animesh is the mayor of n00b_land - a city known for it's massive production of antidepressants.

The rise in demand for such medications have attracted M avaricious businessmen, conveniently numbered from 1 to M, from all around the world. There are N factories in n00b_land - and each factory is owned by one of the M businessmen. Again, the factories are conveniently numbered from 1 to N. Moreover, some factories are dependent on other smaller factories to obtain their raw material. There are N - 1 dependencies in total. Factory numbered 1 is main factory and is not dependent on any other factory. For each factory numbered from 2 to N, it depends on exactly one other factory which has strictly lower index than it.
In other words, the network of dependencies between factories form a tree rooted at 1.

Every year, some factory F earns an amount X as donation from the generous people of pr0_land. The pr0 people of pr0_land ask the factory to distribute wealth in the following manner :

1) Add X to F.
2) Add X + D to all factories which are dependent on F.
3) Add X + 2*D to all factories which are dependent on any factory from step (2).
In general, add X + (K) * D to a factory G if there are K dependencies en-route from F to G.

The businessmen in n00b_land do not care about the welfare of the workers in the factories. As a result, they take all the money that a factory receives by donation from the pr0 people of pr0land.
Further, each businessman has a value Threshold(i), denoting the amount the ith businessman wants to earn.

Given the reports for Q consecutive years (Years are numbered 1..Q), your task is to find the year after which the ith businessman would have earned atleast Threshold(i).

Input Format :

The first line of input comprises space separated integers N and M.

The second line consists of N - 1 space separated integers . Here, ith integer parent[i] denotes parent of (i + 1)th numbered node.

The next line comprises N space separated integers :
The ith integer B[i] denotes the index of the businessman who owns the factory numbered i.

The next line comprises M space separated integers:
The ith integer threshold[i] denotes threshold money for ith businessman

The next line of input comprises one integer Q.
The next Q lines comprises three integers (F, X, D) each.

Constraints :

1 <= N <= 5 * 105
1 <= M <= 5 * 105
1 <= Q <= 5 * 105
1 <= parent[i] <= i
1 <= B[i] <= M
1 <= threshold[i] <= 1018
1 <= F <= N
1 <= X <= 106
0 <= D <= 106

For 15% tests, N,M,Q <= 2000
For 25% tests, D = 0
For rest, orignal constraints

Output Format :

Print M lines, where the ith line denotes the year after which the ith businessman earns his desired amount. If he doesn't earn it throughout the course of the Q years, print "rekt". (without quotes)

3 3
1 2
1 2 3
10 15 20
1 2 3
2 2 3
3 5 10
1 4 0
1 3 3

We have 3 factories, 2nd is dependent on 1st and 3rd is dependent on 2nd.

We have an information about 5 years. Let's see what's happening in first two years.

In 1st year 1st factory gets 2; 2nd factory is dependent on 1st and therefore gets 2+3; 3rd factory is dependent on 2nd, so it gets 2+3*2.

In 2nd year 2nd factory gets 2 and 3rd factory gets 2+3 because it depends on 2nd factory.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

May Circuits

View All Notifications