Flood fill from all 0. If x_i don't have to be, we just set them as 1. For all ?s,

• ? can't be 1 if it can't reach any x_i = 1.

• ? can't be 0 if there exists some c_i = 1 such that, if ? becomes 0 they can't reach any x_i = 1.

We can check them independently. So let's do that.

First part can be easily checked in O(N) for each c_i.

Second part can be checked in O(N^2) for each c_i naively. However, if we run bfs from any x_i = 1, which can't be reached by that ?, we can determine if there exists that c_i. So it can be reduced to O(N) per ?. total O(N^2)

https://github.com/koosaga/olympiad/blob/master/Croatia/coi17_ili.cpp

If we have the spanning forest, component size = |V| — |E|. Group each column's consecutive 1s as one node. Now let’s make spanning forest for [0, N-1]. Some edges will be in spanning forest, but some are not. However, you can observe that the graph is planar. So we can calculate the cycle which that edges belong. (we should do it enough smart to maintain O(NM) time complexity) If the cycle goes broken, then we should use that edge.

In conclusion, we can know what edges do [i, N-1] spanning forest contains. This also enables us to know what edges do [i, j] spanning forest contains. To solve it faster, for each edge and vertex, compute how many interval uses them. You can do some math to figure out that.

Some details are omitted as they are hard to explain. My implementation is about 100 lines, so it’s not that long.

total O(NM * Ackermann(NM)) https://github.com/koosaga/olympiad/blob/master/Croatia/coi17_raspad.cpp

We can carefully model the given structure as a grid graph. Something like :

                      (N-3, 2) - ........
                         |
           (N-2, 1) - (N-2, 2) - (N-2, 3) - ........
                |                  |
(N-1, 0) - (N-1, 1) - (N-1, 2) - (N-1, 3) - ........
    |                    |
(N  , 0) - (N  , 1) - (N  , 2) - (N  , 3) - ........
                |                  |
           (N+1, 1) - (N+1, 2) - (N+1, 3) - ........

Every block has a center. If the center's position is (X, Y), We color that block as (X + 3 * (Y mod 2)) mod 6 + 1. It's not hard to prove that for every placement this coloring works. So we need to find any block placement which completely covers the grid. I found that with O(4^N * N^2) bitmask dp. I think constant factor is not that bad.. but eh, let's see. https://github.com/koosaga/olympiad/blob/master/Croatia/coi17_trapezi.cpp

Do centroid decomposition. Say the centroid is "(", then we append some others to make it as L(R. Find all possible L, and (R with DFS. correct L should look like ((( + expression + (( + expression + ... . For R it's simillar. Now we find all pairs of correct L and correct R, with same extra ( and )s. this can be done by storing counts. total O(NlgN) https://github.com/koosaga/olympiad/blob/master/Croatia/coi17_zagrade.cpp