Offline queries sorted by threshold

Offline queries sorted by threshold answer many questions of one kind at once: can u reach v using only links whose weight is below a limit? When every question is known before the first answer is due, the questions may be answered in any order. Sorted by limit, each question allows every link the previous one allowed and perhaps more, so a single union-find can grow from one question to the next instead of being rebuilt, and each answer is two finds. When the questions arrive one at a time instead, a merge tree built from the sorted links answers each one alone. A search per question, the obvious method, does the whole network’s work again for every question.

The problem: buses on flooded roads

After a storm, a city’s roads are flooded to different depths. The city has n junctions, numbered 0 to n − 1, and roads (a, b, depth) that join two junctions both ways. A bus with a limit of L centimetres can use a road only when the water on it is strictly below L. Each question (u, v, L) asks whether a bus with limit L can get from u to v; answer them all, in the order they were asked. Limits: n, the number of roads and the number of questions are each at most 100,000, and depths and limits are at most 10⁹.

1. Roads 0–1 (30), 1–2 (10), 2–3 (45), 0–3 (60) and 3–4 (20) answer (0, 2, 31), (0, 3, 45), (0, 3, 46), (2, 4, 21) and (4, 4, 1) with yes, no, yes, no and yes. A limit of 45 is not enough for the 45 cm road, and a bus is always at its own junction.
2. Two roads between 0 and 1, of 50 and 20 cm, answer (0, 1, 21) with yes and (1, 0, 20) with no.

The brute force, and why it fails at this size

For each question, search from u over the roads whose water is below its limit, and see whether the search reaches v:

# The brute force: for every question, a breadth-first search over the roads whose water is below the bus's limit.
# Correct by construction, so it is what faster code is checked against.
import random
from collections import deque


def can_travel_brute(n, roads, questions):
    """For each question (u, v, limit): can a bus reach v from u on roads whose depth is strictly below the limit?"""
    links = [[] for _ in range(n)]
    for a, b, depth in roads:
        links[a].append((b, depth))
        links[b].append((a, depth))
    answers, looks = [], 0
    for u, v, limit in questions:
        seen, queue = {u}, deque([u])
        while queue and v not in seen:
            for w, depth in links[queue.popleft()]:
                looks += 1
                if depth < limit and w not in seen:
                    seen.add(w)
                    queue.append(w)
        answers.append(v in seen)
    return answers, looks


roads = [(0, 1, 30), (1, 2, 10), (2, 3, 45), (0, 3, 60), (3, 4, 20)]
questions = [(0, 2, 31), (0, 3, 45), (0, 3, 46), (2, 4, 21), (4, 4, 1)]
answers, looks = can_travel_brute(5, roads, questions)
print("example 1:", answers, f"after {looks} road looks")
answers, looks = can_travel_brute(2, [(0, 1, 50), (0, 1, 20)], [(0, 1, 21), (1, 0, 20)])
print("example 2:", answers, f"after {looks} road looks")

rng = random.Random(15)
for n in (500, 1_000, 2_000):
    roads = [(i, rng.randrange(i), rng.randint(1, 100)) for i in range(1, n)]  # a random tree of roads
    questions = [(rng.randrange(n), rng.randrange(n), 101) for _ in range(n)]  # every road usable: worst case
    _, looks = can_travel_brute(n, roads, questions)
    print(f"{n:>5,} junctions, roads and questions: {looks:>9,} road looks")

example 1: [True, False, True, False, True] after 20 road looks
example 2: [True, False] after 4 road looks
  500 junctions, roads and questions:   210,211 road looks
1,000 junctions, roads and questions:   890,910 road looks
2,000 junctions, roads and questions: 3,557,726 road looks

When every road is usable, each search can cover the whole network, so doubling n and the number of questions multiplies the work by four. At the limits that is up to 10⁵ questions × 2 × 10⁵ road looks, about 2 × 10¹⁰: hours of Python, and still minutes of C++.

What to notice

• All the questions are given before any answer is needed, so they may be answered in any order.
• A higher limit never removes a road: the roads usable at one limit are usable at every higher one.
• A question needs only whether two junctions are connected, which is what a union-find answers.

Sorting both lists, step by step Pro: opens with a Pro, Premium or Ultimate pass