# Velox **URL:** \ **Category:** Aiuto\ **Created:** [27 Gennaio 2015, 8:45pm UTC](https://forum.olinfo.it/t/velox/3889 "2015-01-27T20:45:44Z")\ **Posts on this page:** 10\ **Page:** 1
**Author:** ![kmfrick](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ba9def/32.png) [@kmfrick](https://forum.olinfo.it/u/kmfrick)\ **Post date:** [27 Gennaio 2015, 8:45pm UTC](https://forum.olinfo.it/t/velox/3889/1 "2015-01-27T20:45:44Z")
Scrivo qui subito perché sennò non ci dormirò la notte…(lol) In gara ho scritto in tipo 10 minuti una soluzione in O(n^2) per questo problema…salvo poi passare le successive 2h a capire perché va in loop in alcuni casi negli ultimi due subtask! Io avevo pensato: considerando i limiti di velocità come proprietà degli archi (come se fossero lunghezze in pratica) e implementando il grafo come array di vector di pair, con una DFS partendo da ogni nodo si esplora il grafo provando tutti i percorsi con limiti crescenti, per poi ritornare la lunghezza del percorso quando non si può più andare avanti. Questi percorsi vanno poi a popolare un vector, che viene scorso alla fine e viene mandato in output il valore più grande. Questo risolve senza problemi i primi subtask, ma negli ultimi 2 in alcuni casi esce dai limiti di tempo. Ora, considerando che il massimo valore di  N è 10^4 e che in altri casi negli stessi subtask il programma sta ampiamente nei limiti, mi vien da pensare che finisca in un loop da qualche parte. Dove sta l’inghippo??? ---
**Author:** ![kmfrick](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ba9def/32.png) [@kmfrick](https://forum.olinfo.it/u/kmfrick)\ **Post date:** [28 Gennaio 2015, 9:07am UTC](https://forum.olinfo.it/t/velox/3889/3 "2015-01-28T09:07:13Z")
L’input è un grafo diretto, ogni arco ha un limite di velocità, chiede di trovare il massimo numero di archi percorribili con limiti di velocità crescenti. ---
**Author:** ![chq.matteo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/c/e8c25b/32.png) [@chq.matteo](https://forum.olinfo.it/u/chq.matteo)\ **Post date:** [28 Gennaio 2015, 2:41pm UTC](https://forum.olinfo.it/t/velox/3889/4 "2015-01-28T14:41:12Z")
Prova a postare il sorgente, se si può (sono nuovo del forum).  ---
**Author:** ![Degiac](https://forum.olinfo.it/user_avatar/forum.olinfo.it/degiac/32/9_2.png) [@Degiac](https://forum.olinfo.it/u/Degiac)\ **Post date:** [28 Gennaio 2015, 2:48pm UTC](https://forum.olinfo.it/t/velox/3889/5 "2015-01-28T14:48:58Z")
Hai un link al problema? ---
**Author:** ![CarlaZZ](https://forum.olinfo.it/user_avatar/forum.olinfo.it/carlazz/32/50_2.png) [@CarlaZZ](https://forum.olinfo.it/u/CarlaZZ)\ **Post date:** [28 Gennaio 2015, 5:54pm UTC](https://forum.olinfo.it/t/velox/3889/6 "2015-01-28T17:54:49Z")
In realtà la soluzione era molto semplice… Se ricordo bene, bastava salvare in ogni arco, partendo da questo, la lunghezza massima del percorso raggiungibile. Fai partire la visita da ogni arco, però se arrivi ad un arco già processato, ovviamente non lo riprocessi. Una specie di programmazione dinamica… ---
**Author:** ![kmfrick](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ba9def/32.png) [@kmfrick](https://forum.olinfo.it/u/kmfrick)\ **Post date:** [29 Gennaio 2015, 1:57pm UTC](https://forum.olinfo.it/t/velox/3889/7 "2015-01-29T13:57:44Z")
[https://drive.google.com/file/d/0BwdVhBTGMF5GSG9VWVlmaHFoQWtLS1F6R1N1Y2x0aWhtQmZB/view?usp=sharing](https://drive.google.com/file/d/0BwdVhBTGMF5GSG9VWVlmaHFoQWtLS1F6R1N1Y2x0aWhtQmZB/view?usp=sharing) Questo è il testo del problema… ---
**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\ **Post date:** [29 Gennaio 2015, 8:30pm UTC](https://forum.olinfo.it/t/velox/3889/8 "2015-01-29T20:30:36Z")
Ti sei salvato le soluzioni dei sotto-problemi? Non penso si possa andare in loop dal momento che devi sempre prendere archi in peso **strettamente** crescente. ---
**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\ **Post date:** [30 Gennaio 2015, 1:00pm UTC](https://forum.olinfo.it/t/velox/3889/9 "2015-01-30T13:00:39Z")
Gabriele ha appena aggiunto i task al correttore 🙂 ---
**Author:** ![gfarina](https://forum.olinfo.it/user_avatar/forum.olinfo.it/gfarina/32/70_2.png) [@gfarina](https://forum.olinfo.it/u/gfarina)\ **Post date:** [30 Gennaio 2015, 1:02pm UTC](https://forum.olinfo.it/t/velox/3889/10 "2015-01-30T13:02:02Z")
Esatto, ho appena caricato tutti i problemi dell’ultima gara. Buon debugging 🙂 ---
**Author:** ![anghelo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/ecc23a/32.png) [@anghelo](https://forum.olinfo.it/u/anghelo)\ **Post date:** [11 Febbraio 2015, 7:43pm UTC](https://forum.olinfo.it/t/velox/3889/11 "2015-02-11T19:43:33Z")
si poteva risolvere anche con una soluzione di dinamica?