Ho tentato di risolvere il problema creando una coda di tuple (id_parente, id_figlio, tipo parentela) e un vettore distanze inizializzato a -1 (tranne il primo a 0). Con un loop che cicla finchè lacoda di tuple non è vuota , prendo l’elemento in testa e lo analizzo, se ne conosco il parente aggiorno il vettore distanze (distanze[id_figlio] = distanze[id_padre] + tipo parentela), se il parente è ancora a -1, inserisco nuovamente la tupla in coda e analizzo la prossima.
Questo algoritmo è lento e non rispetta i tempi per fare 100 (infatti fa solo 70 andando fuori tempo negli ultimi testcase della 4 subtask).
Ho pensato quindi ad una analisi dove le relazioni(tuple) fossero gia ordinate in modo di non dover rianalizzare piu volte la stessa; ho trasformato la coda in un vettore per ordinarlo secondo l’id_parente, in modo di avere sempre una relazione possibile da analizzare ma questa soluzione non sembra giusta perchè prendo solo 10 punti con persino la 2nda subtask errata in 3 testcase.
Ho provato a fare una dfs creando un grafo pesato per cercare la massima profondita ma va’ in LTE. Consigli ?
Ciao, con la dfs sei nella giusta strada, prova a ragionare sul fatto che il grafo è un albero e se non riesci a risolverlo prova a postare il codice.
Sono riuscito a risolvere il problema con una bfs. grazie per l’aiuto comunque .
Se a qualcuno interessa lascio qui sotto il codice.
https://pastebin.com/vm1dfKNn
Ciao a tutti,
senza scomodare dfs o bfs, ho pensato di ordinare gli elementi in base al parente noto e scorrere la permutazione così da calcolare prima i parenti vicini allo zero. Questa idea mi da solo 10 punti e non mi è chiaro il motivo.
Potreste aiutarmi a capire qual è il problema? Vorrei evitare di vedere la soluzione proposta da davdag24. Se vi viene in mente un test case che smentisca il mio approccio, fatemi sapere 
Grazie a tutti ragazzi!
Ok risolto. A chi interessasse riporto un test case che fallisce con l’approccio basato su ordinamento
4
P 2
P 3
P 0
Una volta ordinati, l’algoritmo farebbe:
- espande nodo 3 perchè dipende da 0
- espande nodo 1 perchè dipende da 2 (2 non ancora espanso!!!)
- espande nodo 2 perchè dipende da 3
Spero possa essere di aiuto ad altri