USACO 2016 December Contest Silver Division - Moocast

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The small constraints of the input allow us to compute each pair of distances and then for each node, we can perform a traversal which helps us find out how many accessible nodes exist from any starting city.

As \(N\) goes up to \(200\), we can try every starting city and print the maximum answer we get.

Source code

The source code in C++ can be seen below.

#include <fstream>
#include <vector>
using namespace std;

struct Cow {
    int x, y, p;
};

int DFS(int v, const vector<vector<int>> &graph, vector<bool> &visited) {
    visited[v] = true;
    int count = 1;
    for (int neighbor : graph[v]) {
        if (!visited[neighbor]) {
            count += DFS(neighbor, graph, visited);
        }
    }
    return count;
}

int main() {
    ifstream cin("moocast.in");
    ofstream cout("moocast.out");

    int N;
    cin >> N;

    vector<Cow> cows(N);
    for (int i = 0; i < N; i++) {
        cin >> cows[i].x >> cows[i].y >> cows[i].p;
    }

    vector<vector<int>> graph(N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) {
                continue;
            }
            int dx = cows[i].x - cows[j].x;
            int dy = cows[i].y - cows[j].y;
            long long distanceSquared = (long long)dx * dx + (long long)dy * dy;
            long long powerSquared = (long long)cows[i].p * cows[i].p;
            if (distanceSquared <= powerSquared) {
                graph[i].push_back(j);
            }
        }
    }

    int maxReach = 0;
    for (int i = 0; i < N; i++) {
        vector<bool> visited(N, false);
        int reachCount = DFS(i, graph, visited);
        maxReach = max(maxReach, reachCount);
    }

    cout << maxReach << "\n";
    return 0;
}