Fișierul intrare/ieșire: flota.in, flota.out Sursă ad-hoc
Autor Cătălin Frâncu Adăugată de Catalin.FrancuCătălin Frâncu •Catalin.Francu
Timp execuție pe test 1.5 sec Limită de memorie 10240 KB
Scorul tău N/A Dificultate normalnormalnormalnormalnormal

Vezi soluțiile trimise | Statistici

Flota

Mândria complexului de agrement de la Șmenu sunt plimbările cu vaporul pe salba de N lacuri legate prin M canale. Un vapor de lățime L poate naviga între două lacuri dacă există o cale între cele două lacuri formată numai din canale de lățime cel puțin egală cu L. Proprietarul complexului, Trăiam Binescu, dorește să cumpere o flotă de vapoare, toate identice, care să deservească toate lacurile. Deoarece prețurile variază pentru vapoare de diverse lățimi, Binescu își notează K lățimi și dorește să afle, în fiecare caz, numărul minim de vapoare necesare.

Date de intrare

Fișierul de intrare flota.in conține, pe prima linie, numerele N, M și K.

Următoarele M linii conțin triplete de numere x y w, semnificând că între lacurile x și y există un canal de lățime w.

Ultimele K linii conțin câte un număr L i, semnificând o posibilă lățime a vapoarelor de cumpărat.

Date de ieșire

În fișierul de ieșire flota.out se vor scrie K linii. Linia i va conține un singur număr, respectiv numărul de vapoare care sunt necesare pentru lățimea L i. Răspunsurile trebuie afișate în aceeași ordine cu întrebările.

Restricții

  • 1 ≤ N ≤ 50.000
  • 1 ≤ M ≤ 1.000.000
  • 1 ≤ K ≤ 100.000
  • Între oricare două lacuri există cel mult un canal. Toate canalele au dublu sens.
  • Lățimile canalelor și ale vapoarelor sunt întregi, pozitive, cel mult egale cu 50.000.

Exemplu

flota.in flota.out Explicație
6 9 5
1 2 5
1 6 10
2 3 40
2 6 20
3 4 5
3 5 35
3 6 80
4 5 15
5 6 60
20
90
3
60
30
 3
6
1
4
3
 Este nevoie de 3 vapoare de lățime 20: unul pentru grupul de lacuri (2, 3, 5, 6) și câte unul pentru lacurile 1 și 4.
Vapoarele de lățime 90 nu pot naviga pe niciun canal, deci este nevoie de câte un vapor pentru fiecare lac.
Vapoarele de lățime 3 pot naviga pe toate canalele, deci este suficient unul singur.
Este nevoie de 4 vapoare de lățime 60: unul pentru grupul de lacuri (3, 5, 6) și câte unul pentru lacurile 1, 2 și 4.
Este nevoie de 3 vapoare de lățime 20: unul pentru grupul de lacuri (2, 3, 5, 6) și câte unul pentru lacurile 1 și 4.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii