USACO 2020 US Open Contest Silver Division - Cereal

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We go through the numbers in reverse, so we have a single pass and simulation, while in ascending order there would be \(N\) simulations. For the simulation we keep a vector to see which cow took which kind of grain, then we check if we can take the grain myself (if it hasn't been taken, or if someone took it before) or if nothing else can be done.

Source code

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

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back

int main() {
    ifstream cin("cereal.in");
    ofstream cout("cereal.out");

    int n, m, i, cerealChoice, idx, temp;

    cin >> n >> m;

    vector<pair<int, int>> cereal(n + 1);
    for (i = 1; i <= n; i++) {
        cin >> cereal[i].first >> cereal[i].second;
    }

    vector<int> takenCereal(m + 1), ans(n + 1);
    int happyCows = 0;
    for (i = n; i >= 1; i--) {
        cerealChoice = cereal[i].first;
        idx = i;

        while (true) {
            if (takenCereal[cerealChoice] == 0) {
                /* if no one else took it */
                takenCereal[cerealChoice] = idx;
                happyCows++;
                break;
            } else if (takenCereal[cerealChoice] < idx) {
                /* we cannot take it from them */
                break;
            } else {
                /* we can claim it */
                temp = takenCereal[cerealChoice];
                takenCereal[cerealChoice] = idx;

                /* it's the last option */
                if (cerealChoice == cereal[temp].second) {
                    break;
                }

                cerealChoice = cereal[ (idx = temp) ].second;
            }
        }

        ans[i] = happyCows;
    }

    for (i = 1; i <= n; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}