I got stuck the problem below. I wrote some code but I do not understand why my code doesn’t work.
USACO 2020 December Contest, Silver
Problem 3. Stuck in a Rut
What I tried to do in my code is that I keep cows going East and North in the different vectors, and then I looped every cow in es vector (vector of cows going east) and ns vector (vector of cows going North) and calculate the intersection time for each and added those data to actions vector which contains Action (killer (the cow which stopped other one), killed (the cow which was stopped) and time that the occurrence happens.)
Lastly, I sorted the actions list according to time in increasing order and tried to calculate the result but I failed somehow. Can you help me, please?
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct Cow{
int x;
int y;
int i;
};
struct Action{
int killer;
int killed;
int time;
};
bool operator<(const Action& a, const Action& b){
return a.time < b.time;
}
vector<Cow> es;
vector<Cow> ns;
vector<Action> actions;
int main() {
int N;
cin >> N;
char c;
int x,y;
for(int i = 0; i<N; i++){
cin >> c >> x >> y;
if(c == 'E'){
es.push_back({x,y,i});
}else{
ns.push_back({x,y,i});
}
}
for(int i = 0; i<es.size(); i++){
auto a = es[i]; // A
for(int j = 0; j<ns.size(); j++){
auto b = ns[j]; // B
if(a.x < b.x && b.y < a.y){
// B kills A
if(b.x - a.x > a.y - b.y){
actions.push_back({b.i, a.i, b.x-a.x});
}
// A kills B
if(b.x - a.x < a.y - b.y){
actions.push_back({a.i, b.i, a.y - b.y});
}
}
}
}
sort(actions.begin(), actions.end());
int is_dead[N]{0};
int killed[N]{0};
for(int i = 0; i<actions.size(); i++){
auto action = actions[i];
if(is_dead[action.killer] == 0 && is_dead[action.killed] == 0){
killed[action.killer] += killed[action.killed] + 1;
is_dead[action.killed] = 1;
}
}
for(int i = 0; i<N; i++){
cout << killed[i] << endl;
}
return 0;
}