|
Titlul: 521 Banuti Scris de: Adrian Diaconu din Septembrie 11, 2007, 14:20:03 Aici puteţi discuta despre problema Banuti (http://infoarena.ro/problema/banuti).
Titlul: Răspuns: 521 Banuti Scris de: Simoiu Robert din Ianuarie 10, 2013, 13:49:31 Iau 20 cu MLE, cum pot optimiza memoria, eu construiesc graful exact ca in solutie, dar sunt relativ cam multe muchii.
Titlul: Răspuns: 521 Banuti Scris de: Mihai Calancea din Ianuarie 10, 2013, 13:53:08 Pai de ce ai retine muchiile?
Titlul: Răspuns: 521 Banuti Scris de: Simoiu Robert din Ianuarie 10, 2013, 14:04:13 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.
Titlul: Răspuns: 521 Banuti Scris de: Mihai Calancea din Ianuarie 10, 2013, 14:26:38 Nu ai nevoie sa memorezi muchiile. Le poti obtine pe loc oricand ai nevoie.
Titlul: Răspuns: 521 Banuti Scris de: Simoiu Robert din Ianuarie 10, 2013, 17:01:25 Am rezolvat, acuma iau 50 pct. cu TLE.
[LE] Gata, merci fain. Titlul: Răspuns: 521 Banuti Scris de: Alex Velea din Noiembrie 11, 2014, 14:09:15 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 |