Without loss of generality, we can assume that a <= b <= c, and we want to find connected components of size a and b, then all the remaining vertices go to the third part.

Let's solve the tree subtask first. Root in the centroid. Let's consider centroid's sons and sizes of their components ($$$a_1$$$, $$$a_2$$$, ..., $$$a_k$$$) respectively. Each of those does not exceed $$$n/2$$$. Clearly, if none of those components has size >= a, it's impossible to find the desired partition. Otherwise, we can just take that component, find first partition there, and find the second partition in the rest of the graph (there are definitely enough vertices there).

Back to the general case. We can pick any spanning tree and solve the problem as if it was a tree problem. If we failed to find a solution, it means that every component has size smaller than a. We will now consider connections between the components and build a new graph consisting of those $$$k$$$ vertices, where each node has some weight $$$a_i$$$, and connections to other components according to the previously ignored non-tree edges. We aim to find a connected part of size at least a in the new graph, and break the DFS as soon as we manage that (!).

If we fail, then it must have been impossible to find the desired tripartition. Otherwise, we can take that component, find a vertices there and other part of the graph will definitely have a connected component of size at least b. Why? The overhead in finding part $$$a$$$ is at most $$$a-1$$$, because otherwise we would have stopped the DFS earlier. Since all the components are connected through the centroid and $$$a <= b <= c$$$, it means that there are at least $$$b$$$ nodes in the rest of the graph.

Thus, we get a very implementable solution. Shoutout for problem setter!

Taking c to be the biggest and having required 2a+b<=n as a consequence which is needed in the process of the solution just plays out in such a satisfying way!

Lemma: assume the graph is biconnected and let $$$x, y$$$ be such that $$$x + y = n$$$. Then there exists a partition of the graph into two connected subgraphs of sizes $$$x$$$ and $$$y$$$.

Proof: find any st-ordering of the vertices of the graph, which can be done in $$$O(m+n)$$$ or $$$O(m \log n)$$$ time. Then, take its prefix of length $$$x$$$ and suffix of length $$$y$$$ as the subgraphs. From the definition of an st-ordering, it's easy to see that they are connected. (end)

Lemma 2: assume the graph is biconnected, but now the vertices have positive weights not exceeding $$$w$$$. Then, if $$$x, y$$$ are such that $$$w + x + y \ge n$$$, then there exists a partition of the graph into two connected subgraphs of total weights at least $$$x$$$ and $$$y$$$.

Proof: find any st-ordering as above. Find the shortest prefix of the ordering with weight $$$\ge x$$$. Its weight will be less than $$$w + x$$$, so the corresponding suffix has weight $$$\ge y$$$. (end)

Now, let's $$$a \le b \le c$$$. Consider the block-cut tree of the graph (slightly modified so that each vertex of the original graph is in this tree; if the vertex $$$v$$$ is not an articulation point, it'll be a leaf connected to the corresponding biconnected component). Find the weighted centroid of such tree (the vertex after whose removal no subtree will contain more than $$$n / 2$$$ original vertices of the graph).

• If this centroid is a biconnected component $$$X$$$ and one of the subtrees of the block-cut tree contains $$$\ge a$$$ original vertices, take that subtree to set $$$A$$$ and its complement to set $$$B$$$. Obviously, $$$|A| \ge a$$$, and $$$B$$$ is connected and $$$|B| \ge \frac{n}{2} \ge b$$$.

• If this centroid is a biconnected component $$$X$$$ and all the subtrees contain $$$< a$$$ original vertices, create a weighted graph contracted to $$$X$$$ where each vertex $$$v \in X$$$ has its weight equal to the size of the component containing $$$v$$$ after removing all the edges in $$$X$$$. Each weight is $$$< a$$$, and $$$2a + b \ge n$$$, so we can apply the algorithm from Lemma 2 on $$$X$$$ to find two connected sets of vertices $$$A$$$, $$$B$$$ with total weights $$$\ge a$$$, $$$\ge b$$$. We can then expand the graph back, taking whole connected components to each set.

• If this centroid is an articulation point and all the components created after its removal have size $$$<a$$$, the construction is impossible.

• If this centroid is an articulation point and one of the components has size $$$\ge a$$$, take it to set $$$A$$$ and its complement to set $$$B$$$. Now, both $$$A$$$ and $$$B$$$ are connected and $$$|A| \ge a$$$, $$$|B| \ge \frac{n}{2} \ge b$$$.

Both of these cases are easy to check in linear time. Therefore, the task itself is solvable in linear time.

First considering the condition:

(*) forall i, j: min(H[x1 − 1][j], H[x2 + 1][j]) > H[i][j].

In order for (*) to be true, we see that (x1 − 1, j) must be the first position such that H[x1 − 1][j] >= H[x2 + 1][j] if we move (x2 + 1, j) up or (x2 + 1, j) must be the first position such that H[x2 + 1][j] > H[x1 − 1][j] if we move (x1 − 1, j) down. From that observation, we can conclude that the number of states (x1, x2, j) satisfying the (*) condition is about O(2 * N * M).

So we can prepare all (x1, x2, j) states as well as (y1, y2, i) states.

After that, we can calculate the number of (x1, x2, y1, y2) states satisfying the problem condition with sweep line and a segment tree in O(N * M * log2(N * M)).

WLOG, assume that a <= b <= c. It's obvious that we always want to pick connected components with size a and b. Considering a spanning tree T from our initial graph G. We find the centroid node in T, called x. After removing x from T, we have m connected components V[1], V[2], ..., V[m]. We repeatedly perform the following operations:

1. If exists i (1 <= i <= |V|) such that |V[i]| <= a, we pick V[i] then stop.

2. Try to find an edge (u, v) such that u in V[i], v in V[j] and i != j. If found satisfied (u, v) go to the 3rd operation, else we stop.

3. We merge two components V[i] and V[j] and then go to the 1st operation.

Suppose that we cannot pick any components with size >= a (stopped at the 2nd operation), which means that we must use x (the centroid node) to create a component with size = a. However, if we use x, in the remaining components, we cannot find any components with size >= b >= a.

In other case, if we found a component V[i] with size >= a, we can use V[i] to create a components with size = a. Now, all we have to do is to prove |G / V[i]| >= b because we know that G / V[i] is a connected component.

Considering two cases:

1. V[i] is not created by merging two components V[x], V[y].

2. V[i] is created by merging two components V[x], V[y].

With case 1, we know that V[i] <= a -> |G / V[i]| = n − a >= n − a − c = b.

With case 2, we know that |V[i]| = |V[x]| + |V[y]| -> |V[i]| < 2 * a -> |G / V[i]| > n − 2 * a >= n − a − c = b.

Naive solution (24 points?) makes vertices for all intersection. We do some optimizations by only building only the following intersections:

• If a horizontal segment intersects $$$s$$$ or $$$g$$$ we make vertices.
• Make vertices for the endpoint of each horizontal segments.
• When the horizontal segment ends, we make an "escape route vertices", where we make vertices for two horizontal segments, vertically adjacent to that endpoint.

Then we run Dijkstra on that graph.