Analysis: Watering the Fields by Fatih Gelgi

The problem description easily reveals the Minimum Spanning Tree solution. Fields are vertices and squared Euclidean distance is the weight of the edge of a field pair. We just need to disregard the edges that are less than C. Then running MST will solve the problem. If there is a field that cannot be reached (all distances to that field is less than C), the output will be -1.

Representing the graph with adjacency matrix requires O(N^2) memory. We can use it since N is small. Note that representing the graph with an adjacency list is not necessary; in fact it complicates the problem. The running time of Prim's MST algorithm on adjacency matrix is also O(N^2) which is sufficient for the problem. The sample code is as follows:

```/* MST with adjacency matrix: O(n^2) */
#include <fstream>

#define MAX 2000

using namespace std;

int n,c,x[MAX],y[MAX],mat[MAX][MAX];

// MST with Prim
int mst()
{
int from[MAX];
bool mark[MAX];
fill(from,from+n,-1);
fill(mark,mark+n,false);

int x=0,l=0;			// start from vertex 0
// initial length of MST is 0
for (int i=0; i<n-1; i++)
{
mark[x]=true;

// expand the vertex and update edges in the queue
for (int j=0; j<n; j++)
if (!mark[j])
if (mat[x][j])	// if there is (x,j) edge
if (from[j]==-1 || mat[from[j]][j]>mat[x][j])
from[j]=x;

// choose the unused edge with minimum length in the queue
x=-1;
for (int j=0; j<n; j++)
if (!mark[j] && from[j]!=-1)
if (x==-1 || mat[from[x]][x]>mat[from[j]][j])
x=j;

// if graph is not connected
if (x==-1) return -1;

// update total cost of mst
l+=mat[from[x]][x];
}

return l;
}

int main()
{
ifstream fin("irrigation.in");
int m;
fin >> n >> c;
for (int i=0; i<n; i++)
fin >> x[i] >> y[i];
fin.close();

// construct the MST graph
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
{
mat[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
// remove the edge from graph if cost is less than c
if (mat[i][j]<c) mat[i][j]=0;
}

ofstream fout("irrigation.out");
fout << mst() << endl;	// write total length of MST
fout.close();
}
```

Although it is not necessary, we can optimize the memory usage and reduce it to O(N). Since the graph is in 2D plane, it is a fully connected graph i.e. any vertex pair has an edge between them. Hence we don't need to keep the matrix. Here's a sample code:

```/* MST with Prim: O(n^2) */
#include <fstream>
#include <algorithm>

#define MAX 2000

using namespace std;

int n,c,x[MAX],y[MAX],dist[MAX];

int main()
{
ifstream fin("irrigation.in");
fin >> n >> c;
for (int i=0; i<n; i++) fin >> x[i] >> y[i];
fin.close();

int k=0,l=0;			// start from vertex 0
// initial length of MST is 0
fill(dist,dist+n,1000000000);

for (int i=0; i<n-1; i++)
{
dist[k]=-1;		// mark used vertices

// explore vertices and update edges in the queue
for (int j=0; j<n; j++)
{
int d=(x[k]-x[j])*(x[k]-x[j])+(y[k]-y[j])*(y[k]-y[j]);
// if (x,j) edge is long enough
if (d>=c && d<dist[j]) dist[j]=d;
}

// choose the unused edge with minimum length in the queue
k=-1;
for (int j=0; j<n; j++)
if (dist[j]!=-1 && dist[j]!=1000000000)
if (k==-1 || dist[k]>dist[j]) k=j;

if (k==-1) break;	// if graph is not connected
l+=dist[k];		// update total cost of mst
}
if (k==-1) l=-1;

ofstream fout("irrigation.out");
fout << l << endl;
fout.close();
}
```