Official Analysis (C++)

Explanation

We can create a graph where the cells of the field are vertices and two adjacent fields are connected by an edge. To find the connected component with at least $\lceil\frac{N^2}{2}\rceil$ vertices, we can use DSU to keep track of the components and add edges in increasing order of cost until we have a connected component that covers at least half of the vertices.

First, iterate over every cell and add the edges between itself and its neighbors to the $\texttt{edges}$ vector. Only add an edge if the current cell has a greater height than its neighbor to prevent adding an edge twice. Then, sort the edges in increasing order of cost. For each edge, unite the sets of the two vertices and stop when the connected component's size is at least $\lceil\frac{N^2}{2}\rceil$.

Implementation

Time Complexity: $\mathcal{O}(N^2 \cdot \alpha(N))$

Copy
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
void init();
bool unite(int a, int b);

struct Cell {
	int i, j;