Catch the Plane (Editorial)

To solve the problem, we use a dynamic programming approach where routes are considered in decreasing order of departure time.

Let's consider the following state:

• The passenger is at station $x$ at time $time$.

What is the maximum probability of reaching the airport on time from $x$ under an optimal strategy? We denote this quantity as best(x, time). The parameter $time$ can take values up to 10^{18}, so the number of states is effectively infinite. If we are standing at a station waiting, the situation only changes at moments when a bus departs. Therefore, we'll consider only bus departure times.

When we compute best(B, S) for a given route, transitions are possible only to states with later times:

• If the bus runs, we move to the point (E, T),

• If the bus does not run, we stay at (B, S) and wait for the next route.

In both cases, the next moment in time is strictly later than the current one. Thus, if we process the routes in decreasing order of departure time, all the necessary future values will already have been computed.

Dynamic Programming Transitions

Consider the following route:

• B \to E, departure $S$, arrival $T$, probability of running $p$

Then there are two possible actions:

$1$. We try to take the bus. If the bus runs, the probability of this event is $p$. In this case, we move to the state (E, T) and then continue acting optimally:

If you arrive exactly at the departure time, there is no time left to board the bus. Therefore, we look for the next departure from station $E$ that is strictly greater than $T$.

If the bus is canceled, the probability of this event is 1 - p. In this case, we remain at station $B$ and wait for the next route:

If several buses depart from the station at the same time, you can attempt to board only one of them. If that bus is canceled, you cannot board another bus from station $B$ at time $S$. You must wait for a route whose departure time is strictly greater than $S$.

$2$. We do not try to take the bus at all. In that case, we move to the next bus at the same station:

Thus, the transition has the following form:

Example

Sort the routes in the first example by station number and departure time. On the right, list the pairs (departure time, route number) sorted by departure time.

Compute the probabilities of arriving at the airport in decreasing order of bus route departure times. The notation time^+ denotes a time strictly greater than $time$.

Algorithm implementation

Define the structure of a bus route, $Route$. It contains:

• $B$ — the starting station (where the bus departs from);

• $E$ — the destination station (where the bus arrives);

• $S$ — the departure time from the starting station;

• $T$ — the arrival time at the destination station;

• $P$ — the probability that the bus will run on the route;

• $value$ — the maximum probability of reaching the airport (station $1$) if the journey starts with this bus and the remaining route is chosen optimally.

struct Route
{
  int B, E;
  long long S, T;
  double P, value;

Bus routes are sorted:

• by departure time $S$

  bool operator<(const Route& r) const
  {
    return S < r.S;
  }
};

The main part of the program. Read the input data.

scanf("%d %d %lld", &m, &n, &k);

Create a list of all routes grouped by departure station. The vector $v$ has size $n$, which is the number of stations. Thus,

• $v[i]$ contains the list of all bus routes departing from station $i$.

vector<vector<Route>> v(n);
for (int i = 0; i < m; i++)
{
  scanf("%d %d %lld %lld %lf", &r.B, &r.E, &r.S, &r.T, &r.P);

The maximum probability of reaching the airport from this route is initially unknown, so we initialize it to $0$.

  r.value = 0.0;

Add route $r$ to the list of routes that start from $r.B$.

  v[r.B].push_back(r);
}

Now we create a dummy route that represents the moment when the passenger is already at the airport (station $1$). Both the starting and ending stations are the airport.

r.B = 1;
r.E = 1;

The probability that this route succeeds is $100\%$.

r.value = 1.0;
r.P = 1.0;

The departure time and arrival time are later than all others.

r.S = k + 1;
r.T = k + 1;

Add this dummy route to the list of routes departing from the airport.

v[1].push_back(r);

For each station $i$, sort all routes departing from that station $(v[i])$ by departure time $S$. This is necessary to efficiently find the next route later using upper\_bound.

for (int i = 0; i < n; i++)
  sort(v[i].begin(), v[i].end());

Create a single processing order for all routes based on departure time so that the dynamic programming can proceed from later routes to earlier ones.

Declare a vector of pairs, $ord$, which stores for each route:

$1$. Departure time $S$.

$2$. Route indices: $i,j$

• $i$ — station number

• $j$ — route number in $v[i]$

Thus, each entry in $ord$ indicates: "Route v[i][j] departs at time $S$".

vector<pair<long long, pair<int, int>>> ord;
for (int i = 0; i < v.size(); i++)
  for (int j = 0; j < v[i].size(); j++)
    ord.push_back({ v[i][j].S, {i, j} });

Sort the vector $ord$ in ascending order of departure times for all routes, regardless of the station.

sort(ord.begin(), ord.end());

The variable $ret$ computes the maximum probability of catching the flight when starting from station $0$ at time $0$.

double ret = 0.0;

Iterate through the routes in decreasing order of departure time, so that for the current route, the value of all future routes (those departing later) has already been computed, allowing us to correctly compute the optimal probability.

for (int itOrd = m; itOrd >= 0; itOrd--)
{

Let us store the departure time of the current route in the variable startTime.

  long long startTime = ord[itOrd].first;

$p$ is a pair of indices that allows us to locate the current route in the array of routes $v$: the route itself is stored in v[p.first][p.second].

  auto p = ord[itOrd].second;

If the departure time startTime > k (meaning it is impossible to catch the plane), we simply skip this route.

  if (startTime > k) continue;

$st$ is the index of the departure station for the current route.

  int st = p.first;

$r$ is the current route for which we compute the $value$.

  Route& r = v[p.first][p.second];

Initialize the $value$ for the current route to zero.

  r.value = 0.0;

$query$ is a temporary object of type $Route$ that is used to find the next route using upper\_bound. We do not use all its fields — only $B$ and $S$, which are needed for comparison during the search.

  Route query;

Configure $query$ for the following scenario: we want to find the first bus from the same station that departs strictly later than the current time $S$, if the current bus is canceled (does not run).

  query.B = r.B;
  query.S = r.S;

We look for the first bus from the same station that departs later.

  auto it = upper_bound(v[st].begin() + p.second, v[st].end(), query);
  if (it != v[st].end())

If such a route exists, increase r.value by the probability of success through it.

    r.value += (1.0 - r.P) * it->value;

Consider the scenario where the bus actually runs. In this case, at time $T$ we arrive at station $E$. We prepare the object $query$ to search for the next route. We formulate the query: "Find a bus that departs from station $E$ later than time $T$".

  query.B = r.E;
  query.S = r.T;

The variable $d$ stores the index of station $E$, where we have arrived.

  int d = r.E;

Search for the next bus after arriving at $E$ in the list of routes $v[d]$ using binary search. Its departure time from $E$ must be strictly greater than $T$, because according to the problem statement, if you arrive exactly at the departure time, you cannot board the bus.

  it = upper_bound(v[d].begin(), v[d].end(), query);
  if (it != v[d].end())

If such a route is found, it means we can transfer to it. Add the contribution of the probability p \cdot best(E, next~route > T).

    r.value += r.P * it->value;

The next option we consider is to skip the current bus. That is, we do not even consider the option of boarding it or not. We wait for the next bus at the same station.

Check if the next bus exists at this station. Recall that the current route $r$ is stored in v[p.first][p.second].

  if (p.second + 1 < v[p.first].size())

If the bus exists and the probability of successfully reaching the airport using it is higher, we update $value$. Here:

• r.value is the probability of success if we try to board the current bus;

• v[p.first][p.second + 1].value is the probability of success if we skip the current bus and wait for the next one.

    r.value = max(r.value, v[p.first][p.second + 1].value);

Update the overall answer. We select the best option only among the buses that depart from the initial (zero) station

  if (r.B == 0) ret = max(ret, r.value);
}

Print the answer.

printf("%.6lf\n", ret);