Problem Summary

N buildings, M sidewalks (edges). Roger starts at building 1 and moves at speed v1. For each building x (from 2 to N), a group of students starts at x, moves at speed v2, and floods every sidewalk. Roger plays to maximize his survival time; the game ends the instant the student front reaches him. Output the survival time as a reduced fraction, once per x.

Constraints: N <= 2000, M <= 5000, 1 <= v1, v2 <= 100, edge lengths <= 10000. Time limit 3.0 s.

The game almost always ends in the interior of an edge, not at a building, so the core of the solution is an edge-by-edge “catch time” computation built on top of two shortest-path searches per query.

Key Quantities

For a fixed query x, define (in real time, seconds):

  • s(v) = time for the students to first reach building v = dist(x, v) / v2.
  • r(v) = the earliest time Roger can be standing at building v, given that he may only travel through space the students have not already taken.

The single most important subtlety in this problem is that r(v) is not simply dist(1, v) / v1. Roger’s shortest route to v may pass through a building the students seize first; that route is physically blocked, and Roger may be forced onto a longer detour (or be unable to reach v at all). So r(v) is a student-aware arrival time that can exceed the unobstructed geodesic time. Computing r(v) correctly is the crux of the problem.

Computing r(v): A Pruned Dijkstra (and why it is correct)

Run two searches per query:

  1. Student Dijkstra from x, unpruned. Standard shortest paths. This gives s(v) for every v. The students spread everywhere regardless of Roger.

  2. Roger’s Dijkstra from building 1, pruned. Standard Dijkstra, with one rule: when a node v is popped, expand its neighbors only if Roger actually wins the race to v, i.e. r(v) < s(v). If s(v) <= r(v), treat v as blocked and do not relax any edges out of it.

The reason this is correct — and the reason it computes detour-aware times rather than raw geodesics — is the propagation rule, not a post-hoc filter:

  • Because a blocked node is never expanded, no shortest path is allowed to route through it. Any node whose only fast route went through a blocked building must instead receive its distance from some surviving alternate route, or remain unreachable. That is exactly the “students block off shortcuts” detour behavior.
  • The value r(v) that Dijkstra assigns when it pops v is therefore the best time Roger can reach v using only buildings he has already won. This is the genuine constrained arrival time, not dist(1, v) / v1.

In other words, the pruning is part of the distance computation itself. The final reachable set is { v : r(v) < s(v) }, and for each such v the value r(v) is the correct time Roger arrives there.

The s(v) == r(v) boundary needs no special case

A same-instant arrival at a building is just a catch at distance 0: the game ends at v at time s(v). This is already what the edge catch-time formulas produce in the limit, so it does not need to be handled as a separate branch. There is no qualitative difference between “caught exactly at the building” and “caught a hair’s breadth onto an edge” — both fall out of the same continuous math. Only the reachable set matters for expansion (r(v) < s(v) lets Roger push onward); the equality simply contributes the candidate time s(v), which the overall max picks up automatically.

Keep the comparison integer to stay exact: scale distances so r(*) and s(*) are integers (multiplying through by v1 * v2 works), and compare dist1[v] * v2 against distX[v] * v1 rather than dividing.

Where the Game Ends: Edge-Level Analysis

Consider one undirected edge {u, v} of length L. The students reach its ends at times s(u) and s(v) and then advance into the edge from each end at speed v2.

Step 1 — When the whole edge is covered (t_full)

The two student fronts (one from u, one from v) meet when the lengths they have advanced sum to L:

v2 * (t - s(u)) + v2 * (t - s(v)) = L
t_full = (L / v2 + s(u) + s(v)) / 2

At t >= t_full, no point on the edge is safe. The meeting point of the two fronts is the last point on the edge to be covered.

Step 2 — Roger entering from u (requires r(u) < s(u))

Roger steps onto the edge at u at time r(u) and walks toward v at speed v1. Two things can catch him:

(a) The front behind him, from u. It is at distance v2 * (t - s(u)) from u; Roger is at v1 * (t - r(u)). They coincide at

t_behind = (v2 * s(u) - v1 * r(u)) / (v2 - v1),   valid only when v2 > v1.

If v1 >= v2, the behind front never overtakes him.

(b) The front ahead of him, from v (head-on). This is the case the naive write-up glosses over, so here is the clean argument:

Roger’s best play is to walk toward v and stop at the meeting point of the two fronts — the last-covered point — and wait there. He is caught at that point at exactly t_full. He would never walk past the meeting point, because beyond it the v-front has already passed, so doing so only gets him caught earlier (head-on). And he cannot do better than t_full anywhere on the edge, since at t_full every point is covered.

So a head-on catch earlier than t_full only occurs on a suboptimal walk that overshoots the meeting point, and Roger simply does not take it. Note also that waiting at the meeting point does not buy extra time: a front is actively arriving there, and against an approaching front, standing still can only get you caught sooner, never later. (Waiting is useful only at a point no front is currently closing on — never at the meeting point.)

Therefore the survival time for entering this edge from u is

t_enter_u = min(t_full, t_behind)     if v2 > v1
t_enter_u = t_full                    if v2 <= v1   (no behind catch)

Step 3 — Roger entering from v (requires r(v) < s(v))

Identical analysis with u and v swapped:

t_behind_v = (v2 * s(v) - v1 * r(v)) / (v2 - v1),   if v2 > v1
t_enter_v  = min(t_full, t_behind_v)  (or t_full if v2 <= v1)

Step 4 — Answer for query x

best = s(1)        # baseline: students catch Roger at his start, building 1
for each edge {u, v} with length L:
    compute t_full
    if r(u) < s(u):  best = max(best, t_enter_u)
    if r(v) < s(v):  best = max(best, t_enter_v)
output best as a reduced fraction

The baseline s(1) covers the case where Roger’s pruned Dijkstra reaches no edge he can step onto — the students simply reach building 1.

Fraction Arithmetic

Every quantity is rational. To stay exact:

  • Keep all Dijkstra distances as integers (scale by v1 * v2 if convenient).
  • Represent each candidate time as a numerator/denominator pair.
  • Compare candidates by cross-multiplication, never floating point.
  • Reduce the final answer by its gcd.

Distances are at most 2000 * 10000 = 2 * 10^7, and v1, v2 <= 100, so intermediate numerators in the catch-time formulas can reach roughly 10^7 * 10^2 = 10^9 before reduction — comfortably inside 64-bit. If you chain multiplications during comparison, use __int128 (or compare carefully) to be safe.

Complexity

For each of the N - 1 queries we run two Dijkstras (O((M + N) log N)) and a linear O(M) edge scan. Total:

O( N * (M + N) * log N )

With N = 2000, M = 5000, log N ~ 11, that is on the order of 2000 * 7000 * 11 ~ 1.5 * 10^8 operations. This is the editorial’s intended O(N M log N) bound; it is not ~10^7 (a common misstatement that conflates the N * M product with the full cost). It fits in 3 s with a tight Dijkstra and a small constant factor — use an adjacency list, a binary-heap Dijkstra, and avoid per-query reallocation.

Edge Cases

  • v1 == v2. The behind-catch formula divides by zero. The resolution is that the gap (s(u) - r(u)) between Roger and the chasing front never closes, so there is no behind catch and t_enter = t_full.
  • Roger reaches everything first (r(v) < s(v) for all v). He survives longest by heading to the hardest-to-reach edge; the max over edges handles this automatically.
  • A direction Roger cannot use (r(u) >= s(u) for endpoint u). The students reach u no later than Roger, so he cannot step onto the edge from u; skip that direction. The r(u) == s(u) sub-case is just a zero-distance catch contributing s(u), not a special branch (see above).