|
•filipb
|
 |
« : Iulie 08, 2006, 09:20:00 » |
|
Aici puteţi discuta despre problema Catun. |
|
|
|
|
Memorat
|
|
|
|
|
•tm_radu
|
|
« Răspunde #1 : Iulie 08, 2006, 14:46:11 » |
|
Care este complexitatea la aceasta problema? am un O(n^2), dijkstra pe liste....
|
|
|
|
|
Memorat
|
Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
|
|
|
|
•filipb
|
|
« Răspunde #2 : Iulie 08, 2006, 14:56:40 » |
|
Djikstra merge si O(M log N)...
|
|
|
|
|
Memorat
|
|
|
|
|
•pauldb
|
|
« Răspunde #3 : Iulie 09, 2006, 08:39:17 » |
|
Exista drumuri de lungime 0?
|
|
|
|
|
Memorat
|
Am zis  |
|
|
|
•filipb
|
|
« Răspunde #4 : Iulie 09, 2006, 08:40:03 » |
|
Toate costurile pe muchii sunt > 0.
|
|
|
|
|
Memorat
|
|
|
|
|
•cos_min
|
|
« Răspunde #5 : Iulie 31, 2006, 20:01:55 » |
|
of chiar nu inteleg dc scot numai 40 de pcte ... restu WA  toate testele care le dau imi merg ( ) |
|
|
|
|
Memorat
|
vid...
|
|
|
|
•devilkind
|
|
« Răspunde #6 : August 01, 2006, 07:27:06 » |
|
pai zi cum faci, eu iau 50 pct si nici eu nu inteleg ce e gresit.
|
|
|
|
|
Memorat
|
|
|
|
|
•cos_min
|
|
« Răspunde #7 : August 01, 2006, 10:46:13 » |
|
prima data stabilesc pt vecinii directi a celor k cetati : distanta si totodata sol[] ( care retine cetate ) si ii pun in heap
dupa care fac dijkstra si verific daca gasesc d[x->vf] > d + x->cost || actualizez d[] si sol[]
sau daca is egale verific dak sol ii mai mic decat sol[x->vf] si actualizez sol[]
km atat ...
|
|
|
|
|
Memorat
|
vid...
|
|
|
|
•azotlichid
|
|
« Răspunde #8 : August 01, 2006, 12:26:23 » |
|
In teste exista muchii cu lungimi mai mari decat 1024. Aveti grija daca folositi restrictiile asupra lungimilor muchiilor in algoritmul de rezolvare. Asta pana cand vom reface testele  |
|
|
|
|
Memorat
|
|
|
|
|
•cos_min
|
|
« Răspunde #9 : August 01, 2006, 12:49:13 » |
|
nu cre k ii de la asta pt k am obtinut 60 de pcte cu un program n*m care nu folosea long long ...
|
|
|
|
|
Memorat
|
vid...
|
|
|
|
•devilkind
|
|
« Răspunde #10 : August 01, 2006, 13:01:06 » |
|
pai pune long long poate iei 100
|
|
|
|
|
Memorat
|
|
|
|
|
•cos_min
|
|
« Răspunde #11 : August 01, 2006, 13:07:22 » |
|
nu mere  sa fie de la implementare? sau nu ii buna ideea? |
|
|
|
« Ultima modificare: August 01, 2006, 17:20:32 de către cos_min »
|
Memorat
|
vid...
|
|
|
|
•Marius
|
|
« Răspunde #12 : August 02, 2006, 12:12:13 » |
|
nu mere sa fie de la implementare? sau nu ii buna ideea? E buna ideea. Eu nu am folosit deloc long long. |
|
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
|
•pauldb
|
|
« Răspunde #13 : August 03, 2006, 10:05:49 » |
|
Eu iau 80 de puncte cu si fara long long. Pe testele 3 si 8 iau WA. Any ideas why?
|
|
|
|
|
Memorat
|
Am zis |
|
|
|
•cos_min
|
|
« Răspunde #14 : August 09, 2006, 22:40:33 » |
|
 100 dupa lungi chinuri ... greseam la refacerea heapului
|
|
|
|
|
Memorat
|
vid...
|
|
|
|
Tabara Mihai
Vizitator
|
|
« Răspunde #15 : Octombrie 06, 2006, 09:18:28 » |
|
NU iau numai 10 puncte. Am facut Dijkstra pe liste.Cu long long iau 0, iar cu long 10. NU ma astept sa iau 100 cu Dijkstra pe liste, insa nici chiar 10  . Imi iese testul 7 corect.In rest TLE pe 3 teste si WA pe 6 teste. Help pls.  [Later Edit] => Mie mi s-ar parea normal sa imi iasa cu Dijkstra pe liste testele pe care am WA...nu? |
|
|
|
« Ultima modificare: Octombrie 06, 2006, 09:46:38 de către Tabara Mihai »
|
Memorat
|
|
|
|
|
•filipb
|
|
« Răspunde #16 : Octombrie 06, 2006, 11:10:31 » |
|
Ai avut grija pentru fiecare nod sa retii raspunsul cel mai mic?
|
|
|
|
|
Memorat
|
|
|
|
|
Tabara Mihai
Vizitator
|
|
« Răspunde #17 : Octombrie 06, 2006, 11:14:35 » |
|
Ai avut grija pentru fiecare nod sa retii raspunsul cel mai mic?
Da...  sol[p->vf] = Inf( sol[p->vf], sol[poz] );
unde Inf(long int, long int) e functia care stabileste numarul de ordine minim. |
|
|
|
|
Memorat
|
|
|
|
|
•devilkind
|
|
« Răspunde #18 : Octombrie 06, 2006, 14:04:41 » |
|
nush dak am inteles eu bine codu tau, dar am impresia ca verifici faci dinre un costul initial si costul vecinilor. la costul vecinilor ar trebui sa aduni si costul muchiei de la vecin la nod.
PS: eu am luat 100 cu djikstra pe liste
|
|
|
|
|
Memorat
|
|
|
|
|
u-92
Vizitator
|
|
« Răspunde #19 : Octombrie 06, 2006, 14:31:58 » |
|
100 cu O(N^2) ?  |
|
|
|
|
Memorat
|
|
|
|
|
•devilkind
|
|
« Răspunde #20 : Octombrie 06, 2006, 14:56:03 » |
|
dap, bine ca oricum am implementat apoi n log n insa luasem 100 si cu n^2
|
|
|
|
|
Memorat
|
|
|
|
|
|
|
Tabara Mihai
Vizitator
|
|
« Răspunde #22 : Octombrie 06, 2006, 19:28:15 » |
|
Uite cam asa arata Dijkstra-ul meu unde f[] tine sirul fortaretelor, Inf e functia care compara numarul de ordine a doua feude, iar sol e vectorul de iesire. |
|
|
|
« Ultima modificare: Octombrie 08, 2006, 22:51:02 de către Tabara Mihai »
|
Memorat
|
|
|
|
|
•cos_min
|
|
« Răspunde #23 : Octombrie 06, 2006, 20:22:22 » |
|
ce ii Inf ?? scrie ce face Inf  |
|
|
|
|
Memorat
|
vid...
|
|
|
|
u-92
Vizitator
|
|
« Răspunde #24 : Octombrie 07, 2006, 11:49:30 » |
|
e gresit ce faci tu acolo la initializare.. for-ul ala de la 1 la k.. nu calculezi minimul pentru nodurile vecine fortaretelor
|
|
|
|
|
Memorat
|
|
|
|
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena