firstly, I calculated earliest arrival time for each vertex. Then, as mentioned above, I assumed that you don't need to arrive more than n minutes later than earliest arrival time for each vertex. Now graph states become (v, t) where v is the vertex you are currently and t is time passed relative to earliest arrival for this vertex. We need to calculate minimum waiting time. We have transitions from (v,t) to (v, t+1) with cost 1, and transition to (to, current_time — D[to] + 1) with cost 0, where to is vertex where we can go and D[to] is earliest possible arrival in this vertex.As costs are 0/1 we can use 0/1BFS

Here is my solution for problem D which passed system tests, but I was unable to prove it. I hope either someone will hack it or provide the proof: Let's first try to minimize total time. I just have state (i, x) for being in vertex i and trying to go on x-th edge outgoing from i. After this my assumption was that in optimal solution (considering minimizing waiting time) you never need to arrive more than n minutes late compared to earliest arrival time in any vertex. But as I said above, I was unable to prove it. Any counterexamples or insights will be appreciated.

[deleted]

Problem G can be solved offline in O(nlogn + qlogn). answer queries in decreasing order of entry time of x. Add the exit time of each vertex v in the corresponding position in the permutation when we process the first query such that tin[x] <= tin[v] In this way, we can guarantee that we've only added vertices that have greater entry time than current x. So we can query for the minimum on segment.

This logo is the cutest thing I have seen in my life

being an expert is cool!!

What difficulty gap are you talking about? In my opinion, D was easier than C