https://training.olinfo.it/#/task/matita/statement
Buongiorno a tutti, sto provando a risolvere matita ma gli ultimi 3 casi vanno in tle, nonostante usi Hierholzer (complessità O(m)) per trovare il cammino euleriano.
Il codice è questo. Qualcuno riuscirebbe a dirmi come posso migliorarlo?
La tua soluzione non è O(m), perché hai O(m) chiamate alla funzione isolato(), che costa sempre di più man mano che viene chiamata per uno stesso nodo - costando nel peggiore dei casi mediamente O(n) per ciascuna chiamata.
Devi trovare un modo di implementare isolato() in O(1) - ad esempio, potresti salvarti un qualche stato relativo a quanti archi sono già stati processati, o qual è l’indice del prossimo arco da controllare, invece che controllare manualmente se ne trovi uno ancora da processare.
Ho sostituito la funzione con un array che conta quanti archi sono ancora “attivi”, ma mi dà comunque 90/100
Sempre per TLE? Puoi postare il nuovo codice?
Sì era sempre per TLE, ma mentre riguardavo il codice per mandarlo mi sono accorta di aver messo gli endl nell’output. Li ho sostituiti con \n e adesso prende 100, non so come avessi fatto a non accorgermene prima hahah. Grazie comunque
1 Mi Piace