Problem #186

sushi

Time limit: 0.55s
Memory limit: 128MB
Input: sushi.in
Output: sushi.out

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,K_i}\).

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.

Cerință

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ă?

Date de intrare

Pe prima linie a fișierului de intrare sushi.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,K_i}\), 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}\).

Date de ieșire

Pe prima linie a fișierului de ieșire sushi.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 și precizări

  • 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

sushi.in

5 1
3 2 3 4
1 1		
2 1	5
1 1		
1 3		
3 1	0

sushi.out

1 4 0 2 7

Explicaţii

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

sushi.in

3 2	
2 2	3
1 1		
1 1		
2 1	0
3 1	1

sushi.out

2 3 2

Explicaţii

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

General info

Uploader: liviu

Author: Vlad Gavrila, Daniel Posdarascu

Source: ONI 2016 XI-XII: Ziua 1 Problema 2

Submissions