Simons and Reconstructing His Roads

Research checked: the official Codeforces editorial/code and an independent upsolve note both point to the same face-basis + DSU solution. The statement here is still the canonical source.

Define a binary variable $x_{i,j} \in \{0,1\}$ for each unit cell, where $1 \le i < n$ and $1 \le j < m$. Also imagine the outside of the grid as a special face with state $0$.

For a vertical edge $w_{i,j}$, the faces on its two sides are cells $(i,j-1)$ and $(i,j)$, where missing cells mean outside. So this edge is reconstructed iff

$x_{i,j-1} \oplus x_{i,j}=1.$

For a horizontal edge $v_{i,j}$, the faces on its two sides are $(i-1,j)$ and $(i,j)$, so it is reconstructed iff

$x_{i-1,j} \oplus x_{i,j}=1.$

This is exactly the same as XORing boundaries of chosen unit squares. Every chosen square toggles four edges, so degrees stay even. Conversely, every even-degree subgraph of a grid is generated by unit face boundaries. If you want the constructive version: scan each strip and recover cell states from prefix XORs of vertical edges; the vertex parity equations then force all horizontal edges to match too. So there is no missing case hiding under the floorboards.

Now compute the beauty of a cell state assignment. Fix one vertical strip $i$. The selected vertical edges are exactly positions where the sequence

$0, x_{i,1}, x_{i,2}, \ldots, x_{i,m-1}, 0$

changes. Therefore they are endpoints of runs of $1$s. If a run is from $l$ to $r$, the contribution from that run is

$w_{i,l}-w_{i,r+1}=\sum_{j=l}^{r}(w_{i,j}-w_{i,j+1}).$

Summing all runs gives

$\sum_{j=1}^{m-1} x_{i,j}(w_{i,j}-w_{i,j+1}).$

The same argument for horizontal strips gives

$\sum_{i=1}^{n-1} x_{i,j}(v_{i,j}-v_{i+1,j}).$

So the whole objective becomes a boring linear sum over cells:

$\sum_{i=1}^{n-1}\sum_{j=1}^{m-1} x_{i,j}\bigl(w_{i,j}-w_{i,j+1}+v_{i,j}-v_{i+1,j}\bigr).$

Let

$a_{i,j}=w_{i,j}-w_{i,j+1}+v_{i,j}-v_{i+1,j}.$

Now handle blocked streets. If a vertical street $w_{i,j}$ is blocked, it must not be reconstructed, so

$x_{i,j-1}=x_{i,j}.$

If a horizontal street $v_{i,j}$ is blocked, then

$x_{i-1,j}=x_{i,j}.$

These are only equality constraints. Use DSU on all cells plus one outside node $0$. For every blocked edge, unite the two neighboring faces. Boundary blocked edges unite a real cell with outside.

After all unions, each DSU component has one shared binary state. The outside component is forced to $0$. Every other component is free: if its total value $S$ is positive, set the component to $1$ and gain $S$; otherwise set it to $0$ and gain nothing. Therefore the answer is

$\sum_{C \not\ni outside} \max(0, \sum_{(i,j)\in C} a_{i,j}).$

The no-street reconstruction always exists, so there is never a feasibility failure.

Complexity is $O(nm\alpha(nm))$ per test case and $O(nm)$ memory. With the global $\sum nm \le 4\cdot 10^5$, this is easily fine.

Sources used for research: official Codeforces editorial, independent upsolve note.