La cineva ii intra in timp cu fstream? mie doar cu stdio imi intra in timp.

link-ul "Participa si tu la Algoritmiada 2012" de pe pagina princpala e broken

Eu am facut cu priority_queue si a intrat in timp. M-am uitat pe sursa ta... Incearca sa citesti cu fstream pentru ca merge mai bine pe infoarena uneori

Am optimizat toate maruntisurile si nu trece. La sursele mele prostia e ca vreau sa modific costul unui element din heap si sa-i mut pozitia in heap. Asta inseamna sa urmaresc pozitia tuturor elementelor in heap si sa folosesc cand trebuie sa le mut pozitia.
La sursa ta vad ca pur si simplu adaugi acelas nod dar cu alt cost. Daca are distanta mica atunci ajunge in varful heapului, daca nu, se pierde si nu ajunge sa-l procesezi vreodata. O sa incerc make_heap cu idea ta sa vad ce iese.
Multumesc!

a reusit cineva sa faca dijkstra de 100 cu make_heap, push_heap si pop_heap?

vreo idee de ce iau memory limit exceeded la solutia asta pentru cazul 2?

Later edit : problem solved, am pus prev[1]=1; in loc de prev[1]=0; 

Editat de moderator: Nu posta de mai multe ori consecutiv pe acelasi subiect, editeaza posturile anterioare.

La metoda bruta stergerea nu e O(L*N) ?

Cautam o solutie pentru mai multe query-uri unde k e variabil. Interesanta ideea cu 2 heapuri pentru k constant.
Trie-ul desi cred ca merge mai incet in O(log(nr de biti)) pare mai usor de implementat.
Pe arborele binar de cautare echilibrat se pot face query-uri pe intervale?
Multumesc!

Salut,
exista o structura asemanatoare unui heap dar in care sa se poata sterge/modifica al k-lea minim?
multumesc!

    In primul caz matricea are 10 linii si 10^6 coloane, cand face parcurgere pe coloane cred ca sare din 10^6 in 10^6 locatii de memorie, iar in al doilea caz are 10^6 linii, 10 coloane si sare din 10 in 10 locatii de memorie.
    Nu stiu cum functioneaza linia de cache, dar m-as astepta sa se strice la fel de rau in ambele cazuri, sau atunci cand sare din 10 in 10 sa mearga mai repede daca face prefetch la mai multe locatii secventiale.
    Am observat ca parcurgerea pe linii(pt ambele matrici, normala si transpusa) dureaza aproximativ la fel de mult ca si cea pe coloane cand matricea are 10 linii si 10^6 coloane.

programul ... face o parcurgere pe coloane, dureaza 0.21s. Daca inversez sa fie N 1000000 si M 10 dureaza 0.36s. de unde vine diferenta, nu face la fel de multe salturi si pentru matricea transpusa?

Cod:

#define M 1000000
#define N 10
int a[N][M];
int main ()
{long i,j;
 for (i=0;i<M;i++)
 {for (j=0;j<N;j++)
  {a[j][i]=1;
  }
 }
 return 0;
}