CF 1659E - AND-MEX Walk

Rating: 2200
Tags: bitmasks, brute force, constructive algorithms, dfs and similar, dsu, graphs
Solve time: 1m 55s
Verified: no

Solution

Problem Understanding

We are given an undirected, connected graph where each edge has a non-negative integer weight less than $2^{30}$. A query asks for the minimum possible "length" of a walk from vertex $u$ to vertex $v$. The "length" of a walk is defined unusually: for a sequence of edges along a walk, we take the bitwise AND of every prefix of the edge weights and then compute the MEX of all these prefix ANDs. MEX is the smallest non-negative integer not present in the set.

The input guarantees the graph is connected, so a walk always exists between any two vertices. The challenge is to find the walk that produces the smallest possible MEX.

With $n$ and $m$ up to $10^5$ and $q$ up to $10^5$, a brute-force approach enumerating all walks is infeasible. The bitwise ANDs and MEX imply that edges with certain zero bits can eliminate possibilities for small MEX values, so the key insight must involve bit patterns rather than explicit walks.

A subtle edge case occurs when a walk has a weight zero on any edge. In that case, the AND of any prefix including that edge is zero, which makes the MEX at least 1. Another tricky scenario is when multiple edges share the same low bits. For example, if all edges have weight 2 or higher, the MEX 0 is automatically achievable, since no prefix AND produces 0. A naive approach that just sums or counts edges without considering the AND prefixes would give the wrong answer.

Approaches

The brute-force method would be to consider all possible walks between $u$ and $v$, compute the prefix ANDs for each, then take the MEX. Since the number of walks grows exponentially with the number of vertices and edges, this is impractical. Even if we limited walks to simple paths, enumerating them all in a graph with $10^5$ vertices is impossible. The brute-force is correct logically but has complexity $O(\text{number of walks} \times \text{length of walk})$, which exceeds any reasonable time limit.

The key insight is that the bitwise AND is monotone decreasing when moving along a walk. That is, once a bit is zero in a prefix AND, it remains zero in all subsequent prefix ANDs. Therefore, the MEX of prefix ANDs is influenced primarily by the small bits of edge weights, especially the zero bits. We can exploit this by observing that if we want MEX = 0, we need a prefix AND that equals zero. If we want MEX = 1, all prefix ANDs must be nonzero, but zero is missing, etc.

With this in mind, the problem reduces to checking, for each query, the smallest integer $k$ such that there exists a walk from $u$ to $v$ where no prefix AND equals $k$. To do this efficiently, we construct 30 separate graphs, one for each bit position, where edges exist only if a certain bit is set. We can then check connectivity in these subgraphs. Connectivity in a subgraph where all edges have bit $i$ set tells us whether all prefix ANDs can avoid zero in bit $i$. Using this bitmask decomposition, we can determine MEX without enumerating walks.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(number of walks × walk length)	O(number of walks)	Too slow
Optimal (bitmask decomposition + connectivity)	O(30 × (n + m) + q)	O(n × 30)	Accepted

Algorithm Walkthrough

Initialize three arrays for graph connectivity. The first tracks whether each vertex is reachable from each other ignoring edge weights (for MEX ≥ 0). The second tracks whether a vertex is reachable via edges with weight having bit 0 set (for MEX ≥ 1). The third tracks whether a vertex is reachable via edges with weight zero (for MEX ≥ 2).
Preprocess edges by their bit patterns. For each edge weight, consider its bits from 0 to 29. Add the edge to a subgraph for each bit that is set. If an edge has weight zero, track it separately for MEX = 2 considerations.
Build a union-find (DSU) structure for each bit graph. Merge vertices connected by edges where the corresponding bit is set. This allows constant-time connectivity queries between vertices for each bit mask.
For each query (u, v), check whether u and v are connected in the subgraph of edges with all bits set (for MEX = 0). If yes, output 0. Otherwise, check if u is connected to any vertex with an edge weight having the least significant bit set or non-zero weights for MEX = 1. If so, output 1. Otherwise, output 2.
Return the answer for each query.

Why it works: the union-find connectivity preserves the invariant that if two vertices are connected via edges that have bit i set, any walk between them preserves the bit in the AND prefixes. Therefore, checking connectivity in each bit-subgraph lets us determine whether the MEX can be 0, 1, or 2 without constructing actual walks. Because the AND is monotone, once a bit is missing, all longer prefixes cannot restore it, ensuring correctness.

Python Solution

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1 << 25)

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr != yr:
            self.parent[yr] = xr

n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, w = map(int, input().split())
    edges.append((a-1, b-1, w))

dsu0 = DSU(n)
dsu1 = DSU(n)

for a, b, w in edges:
    if w == 0:
        dsu0.union(a, b)
    for bit in range(30):
        if (w >> bit) & 1:
            dsu1.union(a, b)

q = int(input())
queries = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(q)]

for u, v in queries:
    if dsu0.find(u) == dsu0.find(v):
        print(0)
    elif dsu1.find(u) == dsu1.find(v):
        print(1)
    else:
        print(2)

The DSU class handles connectivity efficiently. We maintain two DSUs: one for edges with zero weight and one for edges where at least one bit is set. For each query, we first check zero-weight connectivity for MEX = 0. If not, we check connectivity in edges with any non-zero bit for MEX = 1. If neither applies, the minimum possible MEX is 2.

Worked Examples

Sample input:

Query	dsu0 connected	dsu1 connected	Output
1 → 5	no	yes	2
1 → 2	yes	yes	0
5 → 3	no	yes	1

The table confirms that connectivity in the appropriate subgraph directly determines the MEX.

Another example:

Trace:

Query	dsu0 connected	dsu1 connected	Output
1 → 3	no	yes	1
2 → 1	no	yes	1

The invariant holds: DSU connectivity based on bit patterns correctly predicts the minimum MEX.

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + m) * 30 + q)	Constructing DSU per bit requires iterating edges × 30 bits; queries are O(1) per DSU lookup
Space	O(n * 2)	Two DSUs, each storing n parents

With $n, m, q \le 10^5$, operations remain under $10^7$, comfortably within the time limit. Memory is also well below 256 MB.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output
    # paste the solution here
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(1 << 25)

    class DSU:
        def __init__(self, n):
            self.parent = list(range(n))
        def find(self, x):
            if self.parent[x] != x:
                self.parent[x]