| Fişierul intrare/ieşire: | sushi2.in, sushi2.out | Sursă | ONI 2016, clasele 11-12 |
| Autor | Eugenie Daniel Posdarascu, Vlad Gavrila | Adăugată de |  Vlad Dumitru-Popescu •depevlad |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 128000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sushi2
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 Ki de mese cu care este conectată direct, cât şi lista ordonată de mese vecine acesteia: Vi,1 , Vi,2 ... Vi,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 Vi,j , va pleca de la masa i spre masa:
- Vi,j+1 , dacă 1 ≤ j < Ki
- Vi,1 , dacă j = Ki.
În plus, dacă un preparat nou este trimis de la masa 1 spre masa V1,1 , ştim că acesta va ajunge la masa i pentru prima oară venind dinspre masa Vi,1 , pentru orice i, 1 ≤ i ≤ N.
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 Vx,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ă?
Date de intrare
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 Ki , urmat de Ki numere naturale: Vi,1 , Vi, 2 ... Vi,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 Vx,y.
Date de ieşire
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.
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.
Exemplu
| 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 |
