013 Parcurgere in latime

[•blasterz]

La BFS tu adaugi in coada fiecare nod cel mult o data! Atunci coada are nevoie de N elemente!
Probabil se confunda BFS cu Bellman-Ford cu coada, cand un nod e introdus in coada de mai multe ori!!!

[•zalman]

ms @klamathix

[•nbibest]

ceva idee de rezolvare in pascal? in c am vazut ceva ciudat...un fel de record..vector..semimatrice habar nam cu stl(sau std ziceati voi pe aici...) dar in pascal nu stiu daca exista asa ceva? ceva poate alocare dinamica sau nu inteleg...

[•BitOne]

Se cheama STL
Am facut o filtrare dupa sursele din pascal care au luat 100pct poate te ajuta http://infoarena.ro/monitor?task=bfs&compiler=fpc&score_begin=100

[•newsabbath]

Buna,

mi-ati putea spune cum vad testele de la problema parcurgere in latime?

[•SpiderMan]

Pe fondul galben ai : De asemenea, poti vedea si testele accesand atasamentele. Dai click pe el si ai acolo testele . ( uite aici un link, http://infoarena.ro/problema/bfs?action=attach-list ) . Test.in inseamna input, iar Test.ok inseamna ce trebuie sa afiseze programul.

[•Bit_Master]

Mie-mi scrie la "scorul tau in arhiva" N/A desi am ultima sursa trimisa are 100 de puncte.

[•SpiderMan]

In arhiva educationala, nu iti arata scorul obtinut, aceasta facilitate va fi adaugata doar la IA 3.

[•Bit_Master]

Si ce e de preferat cand lucrezi cu cozi?
deque sau queue?

[•S7012MY]

Si ce e de preferat cand lucrezi cu cozi?
deque sau queue?

Depinde de ce ai nevoie. Daca la un capat doar adaugi si la celalalt doar stergi atunci foloseste queue

[•Bit_Master]

Cum se citesc numerele din fisierul de iesire la evaluare?
Ca am vazut ca daca afisezi cu format " %i" in loc de "%i ", iei 0 in loc de 100.
Adica daca erau string-uri era clar ca conta. Dar vad ca si la numere conteaza daca afisezi un spatiu in fata.

[•Marius_m]

Care credeti ca ar fi cauza de iau time limit exceeded?Implementare cu STL.http://infoarena.ro/job_detail/633394?action=view-source

[•soriyn]

Nu ai complexitatea buna. Tu faci cate un bfs pt fiecare nod. Ideea e sa il faci doar odata pt toate nodurile si retii intr-un vector rezultatele. Datele de intrare fiind mari s-ar putea sa ajute si citirea cu streamuri. Si apropo, sper sa nu gresesc, dar nu are niciun efect acel long 

[•VisuianMihai]

Am si eu o nelamurire. Am de exemplu N=4(nr noduri) si M=3(nr drumuri), iar drumurile sunt asa:
1 2
1 3
4 1
Inteleg ca daca adaug fiecarui nod toti vecinii, adica v[ x ].push_back(y) si v[ y ].push_back(x), irosesc multa memorie, dar daca dau doar v[ x ].push_back(y) si fac BFS din nodul 1, nu risc sa nu treaca prin nodul 4???

[•klamathix]

Nu irosesti memorie. E necesar sa le tii pe ambele directii.

[•Sapientia]

Imi poate explica cineva de ce iau Killed by signal pe toate testele..dupa calculele mele nu am depasit memoria disponibila...sursa:http://www.infoarena.ro/job_detail/1019769?action=view-source

[•PlayLikeNeverB4]

2 ≤ N ≤ 100 000

#define Nmax 1000

[•Sapientia]

http://www.infoarena.ro/job_detail/1019765?action=view-source-aici am pus 5000..si tot aceiasi chestie e.Nu ar trebui sa prind cateva teste?

[•PlayLikeNeverB4]

Poate nu exista astfel de teste. De ce nu vrei sa pui cat trebuie?

[•Sapientia]

Daca puneam cat trebuie depaseam memoria disponibila...oricum acum am implementat in algoritm un deque si am optinut 50 de puncte  Am vazut la o sursa de 100 p ca nu a implementat tablouri bidimensionale..astfel ca i-a ajuns memoria.. nu am nici cea mai mica idee cum se face cu tablouri unidimensionale.

[•PlayLikeNeverB4]

Poti implementa graful cu liste de adiacenta.

[•Sapientia]

Si daca implementez liste de adiacenta,fara sa le aloc dinamic (tot un tablou bidimensional),pierd cumva timp de executie?sau doar memorie?

[•PlayLikeNeverB4]

E mai rau din toate punctele de vedere.

[•serbanalex2202]

Buna seara ,am facut problema aceasta si cea cu sortarea topologica in java si la ambele am runtime error nu inteleg de ce

[•SergiuV]

Buna seara!
Primesc aceasta eroare:
Eroare de compilare:
Main.java:8: error: class Bfs is public, should be declared in a file named Bfs.java
public class Bfs {
^
1 error

si nu inteleg pentru ca m-am asigurat ca numele sursei coincide cu numele clasei.