USACO 2022 US Open Contest Bronze Division - Alchemy

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

A key observation is that the graph is a tree which makes a lot of things easier.

From there, we can think at binary searching for the answer and check at each step whether achieving a certain answer is feasible.

Source codes

The source codes in C++ and Python can be seen below.

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

vector<vector<int> > v;
vector<int> cnt, nec;
int main() 
{
    int n;
    cin >> n;

    cnt.resize(n+1);
    nec.resize(n+1);
    for(int i = 1; i <= n; i++)
        cin >> cnt[i];

    int k;
    cin >> k;
    v.resize(n+1);

    while(k--)
    {
        int a, b;
        cin >> a >> b;
        while(b--)
        {
            int x;
            cin >> x;
            v[a].push_back(x);
        }
    }

    int L = cnt[n] + 1;
    int R = 1000000;
    int ans = cnt[n];

    while(L <= R)
    {
        int mid = (L + R) / 2;
        for(int j = 1; j <= n; j++)
            nec[j] = 0;
        nec[n] = mid;
        for(int nod = n; nod >= 1; nod--)
        {
            nec[nod] = min(10000000, max(0, nec[nod] - cnt[nod]));
            if(v[nod].size())
            {
                for(auto x : v[nod])
                    nec[x] += nec[nod];
                nec[nod] = 0;
            }
        }
        bool ok = 1;
        for(int i = 1; i <= n; i++)
            if(nec[i])
                ok = 0;
        if(ok)
            ans = mid, L = mid + 1;
        else
            R = mid - 1;
    }

    cout << ans;
    return 0;
}

n = int(input())
cnt = [0] + list(map(int, input().split()))
k = int(input())
v = [[] for _ in range(n + 1)]
for _ in range(k):
    vx = list(map(int, input().split()))
    for pos in range(2, len(vx)):
        v[vx[0]].append(vx[pos])
L = cnt[n] + 1
R = 1000000
ans = cnt[n]
while L <= R:
    mid = (L + R) // 2
    nec = [0] * (n + 1)
    nec[n] = mid
    for nod in range(n, 0, -1):
        nec[nod] = min(10000000, max(0, nec[nod] - cnt[nod]))
        if v[nod]:
            for x in v[nod]:
                nec[x] += nec[nod]
            nec[nod] = 0
    ok = True
    for i in range(1, n + 1):
        if nec[i]:
            ok = False
            break
    if ok:
        ans = mid
        L = mid + 1
    else:
        R = mid - 1
print(ans)