== include(page="template/taskheader" task_id="sushi2") ==
Poveste şi cerinţă...
După o zi productivă de făcut curăţenie, Henry şi Hetty au ieşit în oraş la un restaurant de sushi. În acest restaurant există $N$ mese unite între ele prin $N-1$ benzi rulante cu dublu sens, astfel încât oricare două mese sunt conectate direct sau indirect prin benzi rulante. Pentru fiecare masă $i$, $1 ≤ i ≤ N$, cunoaştem atât numărul $K{~i~}$ de mese cu care este conectată direct, cât şi lista ordonată de mese vecine acesteia: $V{~i,1~} , V{~i,2~} ... V{~i,Ki~}$ . Benzile rulante au rolul de a transporta preparatele la clienţi. Acestea urmează un traseu unic, definit după următoarea regulă: pentru orice masă $i$, un preparat aflat la masa $i$ care tocmai a venit dinspre masa $V{~i,j~}$ , va pleca de la masa $i$ spre masa:
* $V{~i,j+1~}$ , dacă $1 ≤ j < K{~i~}$
* $V{~i,1~}$ , dacă $j = K{~i~}$.
În plus, dacă un preparat nou este trimis de la masa $1$ spre masa $V{~1,1~}$ , ştim că acesta va ajunge la masa $i$ pentru prima oară venind dinspre masa $V{~i,1~}$ , pentru orice $i$, $1 ≤ i ≤ N$.
h2. Cerinta
Henry şi Hetty au intrat în restaurant la momentul de timp $0$. Ei ştiu că pe parcursul vizitei lor pe benzile rulante vor fi aşezate $M$ preparate. Pentru fiecare din cele $M$ preparate ei cunosc tripletul $(x, y, t)$, semnificând faptul că la momentul de timp $t$ preparatul va fi aşezat pe bandă în dreptul mesei $x$ pentru a pleca spre spre masa $V{~x,y~}$. Ei mai ştiu şi că timpul necesar unui preparat de a parcurge distanţa dintre două mese vecine este de o unitate. Cei doi se vor aşeza la o masă şi vor lua de pe bandă toate preparatele care trec prin dreptul mesei respective. Henry şi Hetty se întreabă: pentru fiecare masă $i$, care este timpul minim după care culeg toate cele $M$ preparate ce vor fi puse pe bandă?
h2. Date de intrare
Fişierul de intrare $sushi2.in$ ...
Pe prima linie a fişierului de intrare $sushi2.in$ se vor afla două numere naturale $N$ şi $M$, reprezentând numărul de mese, respectiv numarul de preparate aflate în restaurant. Pe următoarele $N$ linii se vor afla descrierile listelor de vecini ale fiecărei mese. Aftfel, pe linia $i + 1$, se va afla numărul natural $K{~i~}$ , urmat de $K{~i~}$ numere naturale: $V{~i,1~} , V{~i, 2~} ... V{~i,Ki~}$ , cu semnificaţia din enunţ. Pe fiecare din următoarele $M$ linii se va afla cate un triplet de numere naturale $(x, y, t)$, semnificând faptul că la momentul de timp $t$ un preparat va fi aşezat pe bandă în dreptul mesei $x$ pentru a pleca spre masa $V{~x,y~}$.
h2. Date de ieşire
În fişierul de ieşire $sushi2.out$ ...
Pe prima linie a fişierului de ieşire $sushi2.out$ se vor afisa $N$ numere naturale, al $i$-ulea dintre acestea reprezentând timpul necesar pentru culegerea tuturor preparatelor de pe bandă dacă Henry şi Hetty s-ar aşeza la masa cu indice $i$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$.
* $1 ≤ M ≤ 100 000$.
* Pentru fiecare triplet $(x, y, t)$ avem $1 ≤ x ≤ N$, $1 ≤ y ≤ K ~x~$ şi $0 ≤ t ≤ 100 000$.
h2. Exemplu
table(example). |_. sushi2.in |_. sushi2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
table(example). |_. sushi2.in |_. sushi2.out |_. Explicatii |
| 5 1
3 2 3 4
1 1
2 1 5
1 1
1 3
3 1 0
| 1 4 0 2 7
| Avem N = 5 mese şi M = 1 preparate.
Masa 1 se învecinează cu 3 mese: (2, 3, 4)
Masa 2 se învecinează cu 1 masă: (1)
Masa 3 se învecinează cu 2 mese: (1, 5)
Masa 4 se învecinează cu 1 masă: (1)
Masa 5 se învecinează cu 1 masă: (3)
Singurul preparat va fi pus la momentul 0 la
masa 3 pentru a pleca spre prima masă din lista
de vecini a lui 3: masa cu indicele 1.
Preparatul va avea următorul traseu: 3, 1, 4, 1,
2, 1, 3, 5, 3 ...
El poate fi ridicat de la:
- masa 1 la momentul 1
- masa 2 la momentul 4
- masa 3 la momentul 0
- masa 4 la momentul 2
- masa 5 la momentul 7 |
|3 2
2 2 3
1 1
1 1
2 1 0
3 1 1
|2 3 2
|Avem N = 3 mese şi M = 2 preparate.
Masa 1 se învecinează cu 2 mese: (2, 3)
Masa 2 se învecinează cu 1 masă: (1)
Masa 3 se învecinează cu 1 masă: (1)
Un preparat este pus la momentul 0 la masa 2
plecând spre prima masă din lista de vecini a
lui 2: masa cu indicele 1. El poate fi ridicat
de la:
- masa 1 la momentul 1
- masa 2 la momentul 0
- masa 3 la momentul 2
Celălalt preparat este pus la momentul 1 la masa
3 plecând spre prima masă din lista de vecini a
lui 3: masa cu indicele 1. El poate fi ridicat de la:
- masa 1 la momentul 2
- masa 2 la momentul 3
- masa 3 la momentul 1
|
...
== include(page="template/taskfooter" task_id="sushi2") ==
