108 Sediu

[•domino]

Aici puteţi discuta despre problema Sediu.

[•alex_prg]

Programul imi trece de compilare si totusi iau 0 puncte cu mesajul RUN ERROR - SIGKILL la toate testele. Am declarat oare o matricea prea mare ?

[u-92]

depinde, daca ai declarat mai mult de 63mb da

[•alex_prg]

am matrice de 16000 pe 16000.   ii prea mult ?

[•svalentin]

cred ca este prea mult

.. calculeaza singur insa cata memorie folosesti:
16000*16000*dimensiunea_tipului
daca este int (sau integer), inmultesti cu 4, daca este long long (sau int64), inmulteste cu 8.. asa vezi exact cat ocupa

oricum, 16000*16000 = 256.000.000, care deja depaseste 64.000.000...

[ditzone]

Pai e aproape 1Giga de memorie ceea ce inseamna foarte mult...
Incearca sa retii arborele prin lista de fii nu matrice de adiacenta...

[•alex_prg]

da ok ... nici nu ma gandeam sa retin arborele cu matrice de adiacenta ... nus batut in cap. Da pentru a construi lista de fii trebuie sa folosesc atuncia O(n^2) care nu intra in timp. nu ? in sensu ca reiau muchiile si caut un varf anume intre printre ele. nu ?

[u-92]

nu, citeste din cormen. Ideea e ca atunci cand aloci dinamic folosesti exact atata memorie cat iti trebuie. Tii pt fiecare nod o lista cu vecinii sai. Complexitatea la parcurgere o sa fie O(N+M)

[•alex_prg]

ok . mersi ... citesc 

[•cos_min]

sunt ceva cazuri speciale la testele 4 si 10 ? Pe restul testelor iau OK, iar pe cele 2 iau WA

[•fireatmyself]

nu par sa aiba nimic iesit din comun. ai testat cum se comporta programul tau si pentru arbori mai speciali? (gen toate nodurile au exact un fiu, sau exact doi...)

[ditzone]

Vezi ca atunci cand exista mai multe sedii trebuie afisate pe aceeasi linie nu pe linii separate.

[•cos_min]

100 .   Codul meu era bun, dar nu afisam pe aceiasi linie  . ms ditzone

[Tabara Mihai]

Imi da si mie cineva un hint la problema va rog....

[u-92]

este explicatia pe situl campion

[•ion824]

Imi poate da cineva un hint ,cam cum ar arata dinamica pe arbore ? nu prea am facut probleme de asa gen..

[•vendetta]

Presupun ca ai facut solutia in n^2... Pt o(n) idea e sa faci o singura parcurgere df si sa reti cateva informatii despre fiecare nod. Iti alegi un nod(o radacina) si apoi faci un df din acel nod; In arborele df ti pentru fiecare nod cate noduri are in subarbore(fie vectorul a[]) si adancimea maxima de la nodul actual pana la o frunza(fie vectorul b[]). Raspunsul va fi minimul din b[]; doar ca dupa ce faci df-ul trebuie sa actualizezi anumite valori din b[] pentru ca tu in Df ai calculat adancimea maxima de la nod in jos dar poate fi si varianta sa fie in sus; si tot ce ramane de facut e sa actulizezi
b[nod] = max(b[nod], n-a[nod]); avand n noduri si tu stiind ca in subarborele cu radacina nod ai a[nod] noduri atunci inseamna ca celalalt drum care exista si nu l-ai luat in considerare in parcurgerea Df va avea n-a[nod] noduri;

[•ion824]

Multumesc mult pentru explicatie, chiar e frumoasa problema. E mai usor decat credeam.