Bruteforce

Najjednoduchšie je odsimulovať zvlášť tok každej kvapky. Vtedy nám stačí udržiavať si pole počtov kvapiek, ktoré už cez jednotlivé údolia pretiekli. Pri každej kvapke potom v každom údolí, do ktorého sa táto kvapka dostane, vieme ľahko spočítať, kam má ďalej tiecť, a to budeme opakovať, až dokým nestečie až k nejakému psíkovi.

Pre všetky údolia na tomto toku si následne zaznačíme, že nimi pretiekla jedna ďalšia kvapka a toto zopakujeme pre každú kvapku.

Takto pre každú z $t$ kvapiek prejdeme potenciálne až tok dĺžky $n$, teda dostávame riešenie s časovou zložitosťou $O(nt)$.

Spracujme viacero kvapiek

naraz

Vo všetkých sadách okrem prvej však musíme spracovať potenciálne až $10^9$ kvapiek, preto nám môže napadnúť, že potrebujeme istým spôsobom spracovať viacero kvapiek naraz. Ako to ale spravíme?

Môžeme si všimnúť, že pri veľkom počte kvapiek sa nám často môže stať, že veľa po sebe nasledujúcich kvapiek tečie presne po tej istej ceste. Pre všetky tieto kvapky tak poznáme odpoveď už po odsimulovaní toku tej prvej z nich - všetky ostatné potom stečú k tomu istému psíkovi ako tá prvá.

Stále však potrebujeme simulovať jednotlivé zmeny toku a po každej zmene toku prejsť celý tok odznova a zistiť, pri ktorom psíkovi tento tok končí.

Vieme si ale všimnúť, že zmien toku v údolí $i$ bude za celú dobu stekania kvapiek najviac $z_i$. Inak povedané, celkový počet zmien toku vo všetkých údoliach dokopy za celú dobu stekania kvapiek bude najviac $\sum z_i$.

Priamočiare riešenie tak mierne vylepšime, aby sme naraz spracovávali všetky po sebe idúce kvapky, ktoré majú úplne identický tok.

Podobne ako v predošlom riešení začneme odsimulovaním toku aktuálnej kvapky. Teraz však pri simulovaní tohto toku súčasne v každom údolí toku určíme, koľko kvapiek doň ešte môže stiecť bez toho, aby sa zmenil smer stekania z daného údolia.

Keď potom vyberieme z týchto hodnôt tú najmenšiu, tak budeme vedieť, koľko ďalších kvapiek ešte stečie po úplne tom istom toku a pri ktorej najbližšej kvapke sa už jej smer stekania v nejakom údolí zmení.

Simulovania celého toku pre tento počet nasledujúcich kvapiek tak vieme preskočiť a všetky tieto kvapky priradiť ku psíkovi, u ktorého skončila aktuálne vyslaná kvapka.

Keď následne budeme chcieť spracovať kvapku, ktorá už má odlišný tok od týchto predošlých, tak musíme prinajhoršom prerátať celý tok odznova (keďže sa napríklad mohol zmeniť smer odtekania už niekde úplne na začiatku toku) a podobne určiť, koľko najbližších kvapiek stečie po tom istom toku. Toto však spravíme nanajvýš $\sum z_i$-krát, keďže nanajvýš toľko zmien v toku kvapiek sa celkovo uskutoční.

Keďže v tomto riešení musíme prerátať celý tok maximálne $\sum z_i$-krát, tak časová zložitosť tohto riešenia je $O(n \cdot \sum z_i)$, čo už stačí aj na druhú sadu.

Optimálne riešenie

Pre získanie plného počtu bodov potrebujeme tok kvapiek simulovať už nie po jednotlivých kvapkách alebo zmenách toku, ale po jednotlivých údoliach. Keď totiž vieme, koľko kvapiek sa celkovo niekedy dostane do nejakého údolia $i$, tak ľahko vieme tento počet rozdeliť do skupín po $k_i$ (ak počet kvapiek v danom údolí nie je deliteľný $k_i$, tak nám ostane jedna posledná skupina, v ktorej bude menej než $k_i$ kvapiek) a každú túto skupinu ďalej pošleme do príslušného ďalšieho údolia, do ktorého bude vtedy voda z tohto údolia stekať.

Vieme si všimnúť, že nám pritom vlastne ani nezáleží na tom, v akom presne čase k nám stečie ktorá kvapka, ale stačí nám vedieť tento celkový počet kvapiek, ktoré do daného údolia niekedy stečú.

Treba si však dať pozor na to, v akom poradí z jednotlivých údolí takto ďalej posielame kvapky. Ak by sme totiž poslali ďalej kvapky z nejakého údolia, do ktorého ale ešte nejaké ďalšie kvapky niekedy neskôr stečú, tak sa nám informácia o týchto kvapkách stratí a tieto kvapky sa nedostanú k jednotlivým psíkom.

Tu sa nám však hodí informácia zo zadania, že voda môže stekať len z vyššie položeného údolia do nižšie položeného údolia a že teda nemôže tiecť do cyklu. Ak by sme si teda celú túto úlohu predstavili ako orientovaný graf, kde vrcholy sú jednotlivé údolia a hrana spája vrcholy $i$ a $j$ práve vtedy, keď niekedy steká voda z údolia $i$ do údolia $j$, tak máme zaručené, že tento graf bude acyklický, teda sa jedná o tzv. DAG (z anglického directed acyclic graph).

Pre každý DAG pritom existuje tzv. topologické usporiadanie jeho vrcholov, teda také usporiadanie jeho vrcholov, pri ktorom sa pre každú hranu jej začiatočný vrchol nachádza v tomto usporiadaní skôr než jej koncový vrchol.

Ak by sme teda v grafe prislúchajúcom tokom kvapiek medzi údoliami našli topologické usporiadanie údolí a posielali by sme kvapky ďalej z jednotlivých údolí v tom poradí, v akom sa tieto údolia nachádzajú v ich topologickom usporiadaní, tak vždy v dobe rozširovania sa z nejakého údolia do ďalších údolí je počet kvapiek v tomto údolí už finálny a vieme ich teda rozposlať ďalej bez toho, aby sa nám nejaké kvapky stratili.

Ostáva nám tak už iba nájsť topologické usporiadanie jednotlivých údolí. To vieme spraviť tak, že pre každé údolie si budeme pamätať, koľko ešte nespracovaných hrán doň smeruje. Pre vrchol, ktorý ako ďalší pridáme do topologického usporiadania, potom musí platiť, že všetky hrany smerujúce doň sme už spracovali a že keď sa k nemu teda v tomto momente dostaneme, tak počet kvapiek v ňom už bude finálny.

Vieme si tak udržiavať pole vrcholov, do ktorých už nesmerujú žiadne nespracované hrany, v každom kroku z tohto poľa nejaký vrchol vybrať a všetky hrany vychádzajúce z neho označiť za spracované tým, že vrcholom, do ktorých smerujú, počet nespracovaných hrán smerujúcich do nich znížime o $1$.

Následne nám už pri tomto aktualizovaní počtu vchádzajúcich nespracovaných hrán stačí len kontrolovať, či pri nejakom vrchole tento počet neklesol na nulu a či ho teda nevieme pridať do poľa vrcholov, ktoré vieme priamo pridať do topologického usporiadania ako ďalšie.

Topologické usporiadanie údolí takto nájdeme v čase lineárnom od počtu vrcholov aj hrán v našom grafe, teda v čase $O(n + \sum z_i)$. Následne údoliu s prameňom priradíme $t$ kvapiek a všetkým ostatným údoliam zatiaľ $0$ kvapiek.

Tieto údolia budeme potom prechádzať v poradí nájdeného topologického usporiadania a počty kvapiek, ktoré do nich stiekli, budeme ďalej rozdeľovať údoliam, do ktorých tieto kvapky stečú. Takto si pre každé údolie so psíkom vo výsledku zaznačíme, koľko kvapiek doň celkovo stieklo a tieto hodnoty vypíšeme.

Aj v tejto časti riešenia s rozdeľovaním kvapiek do ďalších údolí spracujeme každý vrchol a každú hranu len raz, teda aj toto prebehne v čase lineárnom od počtu vrcholov a hrán. Celková časová zložitosť tohto riešenia je tak $O(n + \sum z_i)$.

n, t = map(int, input().split())
K = []
postupnosti = [[] for _ in range(n)]
hrany_do = [0 for _ in range(n)]

for i in range(n):
    A = list(map(int, input().split()))
    K.append(A[0])

    if A[0] != 0:
        for j in range(1, len(A)):
            postupnosti[i].append(A[j])
            hrany_do[A[j]] += 1

toposort = []
for i in range(n):
    if hrany_do[i] == 0:
        toposort.append(i)

kvapky = [0 for _ in range(n)]
kvapky[0] = t

while len(toposort) > 0:
    v = toposort.pop()

    kvapiek = kvapky[v]
    for u in postupnosti[v]:
        hrany_do[u] -= 1
        if hrany_do[u] == 0:
            toposort.append(u)
        if kvapiek > K[v]:
            kvapky[u] += K[v]
            kvapiek -= K[v]
        else:
            kvapky[u] += kvapiek
            kvapiek = 0

for i in range(n):
    if K[i] == 0:
        print(kvapky[i])

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n,t; cin >> n >> t;

    vector<vector<int>> graf (n);
    vector<int> menia_sa (n);
    vector<int> inc(n,0);
    vector<int> prislo_kvapiek(n,0);
    prislo_kvapiek[0] = t;

    for (int i = 0; i < n; i++)
    {
        cin >> menia_sa[i];
        if (menia_sa[i])
        {
            for (int g = 0; g< (t-1)/menia_sa[i] + 1; g++)
            {
                int to; cin >> to;
                graf[i].push_back(to);
                inc[to] ++;
            }
        }
    }

    vector<int> stack_udoli;
    for (int i = 0; i < n; i++)
    {
        if (inc[i] == 0)
        {
            stack_udoli.push_back(i);
        }

    }

    int ind = 0;

    while (stack_udoli.size() > ind)
    {
        int vtx = stack_udoli[ind];
        int tecie = menia_sa[vtx];
        int kvap = prislo_kvapiek[vtx];
        if (!tecie)
        {
            ind++;
        } else
        {
            for (int i = 0; i < graf[vtx].size(); i++)
            {
                int kam = graf[vtx][i];
                prislo_kvapiek[kam] += min(kvap,tecie);
                kvap -= min(kvap,tecie);
                inc[kam] -= 1;
                if (!inc[kam])
                {
                    stack_udoli.push_back(kam);
                }
            }
            ind ++; 
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (menia_sa[i] == 0)
        {
            cout << prislo_kvapiek[i] << endl;
        }

    }
}