InThePathToMosque
SRM 767 · 2019-09-17 · by minimario
Problem Statement
Mojtaba lives in Tehran. Tehran is a city with n squares and n-1 streets such that all of the squares are connected. The streets may have different lengths. The squares are numbered from 0 to n-1. The Grand Mosque of Tehran is at the square number 0.
Tehran can be viewed as a rooted weighted tree. The node number 0 is the root. You are given the description of the tree: for each i > 0 you are given the numbers par[i] and w[i]. Here, par[i] is the parent of node i, and w[i] is the length (in kilometers) of the street from i to par[i]. Note that the tree is numbered in such a way that par[i] < i for all i >= 1.
It's Friday and q people are going to travel from their homes to the Grand Mosque. The people will travel one at a time, in the given order. More precisely, person i+1 will start their journey only after person i parks their car and finishes their journey.
The cars consume 1 liter of fuel per kilometer.
In general, the journey of a person looks as follows: Somewhere in Tehran there are cars parked by the previous travelers, and there may be some fuel available in them. (The Iranians are kind, so they leave their fuel leftovers available for other travelers to the mosque.) Person i starts from the square u[i] where they live. When they start their journey, they are in their car and the car has f[i] liters of fuel. Each person follows the same simple algorithm:
while you are not at the Grand Mosque:
let X be your current square
collect all the fuel available in the cars parked at square X, and put all that fuel into your car
let F be the amount of fuel you now have
if F >= w[X]:
travel from X to par[X], which consumes w[X] liters of fuel
upon arrival to par[X], receive 2*w[X] liters of fuel from the locals
else:
park your car at square X
walk from there to the Grand Mosque
After each person finishes their trip to the mosque, the locals in all the squares will refill all the fuel that was taken from the parked cars. Hence, once somebody parks a car somewhere and leaves L liters of fuel in that car, each future traveler will have those L liters available at that location.
The input is generated pseudorandomly, using parameters A, B, and t Use the following pseudocode:
par[1] = 0
for i = 2 to n-1:
par[i] = Max(0, i - 1 - ((par[i - 1] * A + B) Modulo t) )
w[1] = B
for i = 2 to n-1:
w[i] = (w[i - 1] * A + B) Modulo 10^9
u[0] = B modulo N
for i = 1 to q-1:
u[i] = (u[i - 1] * A + B) Modulo n
f[0] = B
for i = 1 to q-1:
f[i] = (f[i - 1] * A + B) Modulo 10^9
For each person, determine the number of the square where they will park their car. Return the sum of those numbers.
Notes
- The queries are not independent and their order matters. Remember that each person may use fuel that was left in the cars by previous travelers.
- The people who reach the mosque in their cars will park next to the Mosque, in the square number 0.
Constraints
- n, q, t will each be between 1 and 100,000, inclusive.
- A, B will each be between 0 and 10^9 - 1, inclusive.
5 10 3 2 1 Returns: 5
10 20 1234567 7654321 13 Returns: 29
100000 100000 103 203 6 Returns: 568527503
100000 100000 154651 134845 100 Returns: 964188963
100000 100000 545118445 514512857 100000 Returns: 3444558
10 20 1234567 7654321 3 Returns: 29
The edges of the tree: x par[x] w[x] 1 0 7654321 2 0 779768328 3 1 253048297 4 1 84536720 5 2 252454561 6 5 77664408 7 6 922845657 8 6 801879840 9 7 396083601 The first few queries: u[i] f[i] 1 7654321 8 779768328 7 253048297 0 84536720 1 252454561 8 77664408 7 922845657
Submissions are judged against all 107 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class InThePathToMosque with a public method long long solve(int n, int q, int A, int B, int t) · 107 test cases · 2 s / 256 MB per case