 # USACO Silver 2020 December - Stuck in a Rut (Link)

## My Work

``````#include <bits/stdc++.h>
#include <vector>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vb = vector<bool>;
using pii = pair<int, int>;

#define endl " \n"
#define size(x) int((x).size())
#define all(a) a.begin(), a.end()
const int mod = 1e9+7, inf = INT_MAX, ninf = INT_MIN;

void setIO(string name = "") {
cin.tie(0)->sync_with_stdio(0);
if (!name.empty()) { freopen((name+".in").c_str(), "r", stdin); freopen((name+".out").c_str(), "w", stdout); }
}

void solve();

int main() {
setIO();
solve();
return 0;
}

struct Cow {
char dir {};
ll x {}, y {};
ll timeStopped {};
bool active = true;
};

struct Event {
ll x {}, y {};
ll time {};
};

// only calculating whether 'a' gets hits by the rut carved by 'b'
ll whenMet(Cow a, Cow b) {
if (a.dir == b.dir) return inf;

// considering 'a' is always moving to north
if (a.dir == 'E') {
swap(a.x, a.y);
swap(b.x, b.y);
}

// 'a' is going north and 'b' is going east
// if 'b' is in the east of 'a' || 'a' is in the north of 'b'
if (a.x < b.x || a.y > b.y) return inf;

// cal time for 'a' & 'b' to reach point of intersection
ll timeA = b.y-a.y, timeB = a.x-b.x;

// if 'a' take more time to reach the point of intersection then it gets hit by a rut and stops
return (timeA > timeB ? timeA : inf);
return timeA;
return inf;
}

void solve() {
int n;
cin >> n;

vector<Cow> cows (n);
for (auto& i : cows) { cin >> i.dir >> i.x >> i.y; i.timeStopped = inf; }

vector<Event> intersection;

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ll t = whenMet(cows[i], cows[j]);
if (t != inf) {
intersection.emplace_back(Event{i, j, t});
}
}
}

// sorting all the point of intersections by time
sort(all(intersection), [](Event& a, Event& b) { return a.time < b.time; });

vector<ll> count (n, 0);
for (auto event : intersection) {
// if both are cows are active i.e moving
if (cows[event.x].active && cows[event.y].active) {
cows[event.x].active = false;
count[event.y] += 1 + count[event.x];
}
}

for (auto i : count)
cout << i << endl;
}

``````

Explanation
I have find all the points of intersections (Intersection represents whether the cowA is getting intersected by the rut carved by cowB) Sorted them my increasing order of time. Then iterating over the sorted vector of intersection checking whether both the cows are moving (active) if so I make cowA stops at that position (by setting it’s active to false) and increase the blame of cowB by 1 + blame of cowA.

## What I’ve Tried

I have tried like 5 test cases. (randomly generated) and then does the simulation (by hand) and I am getting the correct result for those.

## Question

Where is it getting wrong ? Is there a way in USACO to see test cases ? It happens a lot & if only I knew where my solution was failing it might give me an insight where my solution is failing and I can improve upon it. Just seeing a wrong answer verdict doesn’t help You can download the test cases if you click on the contest page that contains the problem

1 Like

thank you