521 Banuti

[•DITzoneC]

Aici puteţi discuta despre problema Banuti.

[•SpiderMan]

Iau 20 cu MLE, cum pot optimiza memoria, eu construiesc graful exact ca in solutie, dar sunt relativ cam multe muchii.

[•klamathix]

Pai de ce ai retine muchiile?

[•SpiderMan]

Nu inteleg intrebarea. Adica eu construiesc lista vector <int> G[MAX_M], unde MAX_M = numarul minim maxim, care este 5000 in acest caz, si apoi fac dijkstra pe acest graf. Dar se pare ca lista asta devine cam "voluminoasa" la un moment dat, si nu stiu ce sa fac.

[•klamathix]

Nu ai nevoie sa memorezi muchiile. Le poti obtine pe loc oricand ai nevoie.

[•SpiderMan]

Am rezolvat, acuma iau 50 pct. cu TLE.
[LE] Gata, merci fain.

[•veleandu]

ceva nu e chiar ok la problema asta
#1 nu cred ca merge in O(N * N). cel putin mie nu mi-a mers.
daca am bagat dijkstra care merge teoretic in O(N * N * logN)

stiu ca teoretic e foarte greu sa iasa O(NNlogN) dar cred totusi ca ar trebui sa mearga mai bine NN pt ca graful e complet.

#2 exista cazuri in care rezultatul e pe int64
nu exista aceasta restrictie si e foarte usor sa gasesti un test care sa iasa de int 32 de biti
2
4999 10^7