Advertisement
tepyotin2

Untitled

Oct 5th, 2023
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<vector<bool>> connected;
  4. vector<bool> visited;
  5. /** @return how many cows can be reached from a cow c */
  6. int reachable_cows(int c) {
  7.     visited[c] = true;
  8.     // we can always reach the initial cow c
  9.     int reached = 1;
  10.     for (int nc = 0; nc < connected.size(); nc++) {
  11.         // make sure we can connect to this cow & it hasn't been reached yet
  12.         if (!visited[nc] && connected[c][nc]) {
  13.             visited[nc] = true;
  14.             reached += reachable_cows(nc);
  15.         }
  16.     }
  17.     return reached;
  18. }
  19. int main() {
  20.     freopen("moocast.in", "r", stdin);
  21.     int cow_num;
  22.     cin >> cow_num;
  23.     vector<int> x(cow_num), y(cow_num);
  24.     vector<int> power(cow_num);
  25.     for (int c = 0; c < cow_num; c++) {
  26.         cin >> x[c] >> y[c] >> power[c];
  27.     }
  28.     connected = vector<vector<bool>>(cow_num, vector<bool>(cow_num));
  29.     for (int i = 0; i < cow_num; i++) {
  30.         for (int j = 0; j < cow_num; j++) {
  31.             int dist_squared = (
  32.                 (x[i] - x[j]) * (x[i] - x[j])
  33.                 + (y[i] - y[j]) * (y[i] - y[j])
  34.             );            
  35.             connected[i][j] = dist_squared <= power[i] * power[i];
  36.         }
  37.     }
  38.     int max_cows = 0;
  39.     for (int c = 0; c < cow_num; c++) {
  40.         visited.assign(cow_num, false);
  41.         max_cows = max(max_cows, reachable_cows(c));
  42.     }
  43.     freopen("moocast.out", "w", stdout);
  44.     cout << max_cows << endl;
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement