Ceva e tare tare naspa la problema asta. Am o solutie care tot ia 50 p astfel:
- primele 4 teste, TLE.
- testul 5, TLE/WA (depinde de optimizari)
- ultimele 5 teste, corecte
Algoritmul meu se compune din:
1. citire - O(m) <- nu se poate scapa de asta
2. un DF <- ca sa determin cate cicluri rosii sunt.
3. niste calcule care duc la solutie. O(2*n) (am pus si constanta).
Am incercat mai multe variante. Simulez listele de adiacenta cu vectori (adica sunt alocate static) ca sa evit sa bag pointeri (nu se prea cunoaste diferenta, 0,01 secunde la testul 5). DF-ul n-ar trebui sa ia mai mult de O(n), avand in vedere ca sunt n noduri. Eu mai fac niste operatii si pentru cazul in care nodul in care incerc sa merg e deja vizitat (totusi, doar 3 adunari !!)...
Ce pot sa ii mai fac? Tot iau TLE. Evident, solutia este liniara. In cazul asta, constanta conteaza mult.