USACO 2023 February Contest Silver Division - Cow-libi

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Given that only one cow can reach all the grazings, we can conclude that if a cow can reach the grazing before and after (if such a cow exists), then it can reach all grazings.

Therefore, we sort the grazings by the time and for every alibi we binary search the two closest grazings to it and check if we can reach them. If this can happen, then the cow is not innocent.

Source code

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

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct event {
    int x;
    int y;
    int time;
};

event grazing[100001];
event alibi[100001];

bool cmp(event a, event b) {
    return a.time < b.time; 
}

unsigned long long mysqrt(unsigned long long x) {
    if (x == 0) 
        return 0;
    unsigned long long rez = sqrt(x) - 1;
    while (rez * rez < x) 
        rez++;
    return rez;
}

bool possible(event a, event b) {
    if (1ULL * (1ULL * mysqrt(1ULL * (1ULL * abs(a.x - b.x) * 1ULL * abs(a.x - b.x) + 1ULL * abs(a.y - b.y) * 1ULL * abs(a.y - b.y)))) <= 1ULL * abs(a.time - b.time)) 
        return 1;
    return 0;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int g, n, i, j, might, r, pas;
    cin >> g >> n;
    for (i = 1; i <= g; i++) {
        cin >> grazing[i].x >> grazing[i].y >> grazing[i].time;
    }
    for (i = 1; i <= n; i++) {
        cin >> alibi[i].x >> alibi[i].y >> alibi[i].time;
    }
    sort(grazing + 1, grazing + 1 + g, cmp);
    might = 0;
    for (i = 1; i <= n; i++) {
        r = 0;
        pas = (1 << 16);
        while (pas) {
            if (r + pas <= g && grazing[r + pas].time <= alibi[i].time) 
                r += pas;
            pas = pas / 2;
        }
        event a, b;
        a = alibi[i];
        b = grazing[r];
        if (r == 0) {
            r++;
            a = alibi[i];
            b = grazing[r];
            if (possible(a, b)) 
                might++;
        } 
        else 
            if (possible(a, b)) {
                if (r != n) {
                    b = grazing[r + 1];
                    if (possible(a, b)) might++;
                } else
                    might++;
            }
    }
    cout << n - might;
}