Editorial for Moocast
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Editorialist:
This question is the third question in the first PCS Standard Contest.
For this question, the first thing we must do is get a list of which cows can directly contact each other (that is \(P_i\leq\sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}\)). We can do this by iterating through each cow and checking whether it can directly contact any of the other cows. Using this, we can generate an adjacency matrix.
Now that we have our adjacency matrix, we can simply DFS (or BFS) from each cow and record which cow is able to read the most number of other cows! This solution is \(O(N^2)\), but will easily run in time.
#include <bits/stdc++.h>
using namespace std;
int main() {
long N;
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
struct cow {
long x;
long y;
long power;
};
vector<cow> cows(N);
for (long i = 0; i < N; ++i)
cin >> cows[i].x >> cows[i].y >> cows[i].power;
map<long, set<long>> cow_list;
for (long i = 0; i < N; ++i) {
long power = cows[i].power*cows[i].power;
for (long j = 0; j < N; ++j) {
long x_diff = cows[i].x - cows[j].x;
long y_diff = cows[i].y - cows[j].y;
long distance_squared = x_diff*x_diff + y_diff*y_diff;
if (distance_squared <= power) {
cow_list[i].insert(j);
}
}
}
long max_cows = 0;
for (auto c : cow_list) { // DFS
set<long> reached_cows;
stack<long> S;
S.push(c.first);
while (!S.empty()) {
long t = S.top();
S.pop();
reached_cows.insert(t);
for (auto cow : cow_list[t]) {
if (reached_cows.find(cow) == reached_cows.end())
S.push(cow);
}
}
if (reached_cows.size() > max_cows)
max_cows = reached_cows.size();
}
cout << max_cows << endl;
}
Comments