206 Arbore

[ditzone]

Aici puteţi discuta despre problema Arbore.

[•andrei_savu]

Cum se face problema asta ?

[•danielp]

Va aparea un articol pe http://info.devnet.ro cu solutiile de la problemele de la finala.

[•gogu]

Mai vrea sa faca cineva articolul ala sau ati uitat de el?
Sau va pregatiti pentru simulari?

[•bogdan2412]

Probabil ca o sa se faca... Daca vrei un hint gandeste-te cum scoti O(sqrt N) pe query / update Daca gasesti o rezolvare cu o constanta destul de mare (in jurul lui 7) incearc-o ca intra in timp

[alex_g]

Pe mine ma termina problema asta.......iau WA la toate testele .......si pe testele mele merge bine.
In problema spune ca e bun indicele oricarui angajat daca acesta a primit suma s  ....numai la afisare poate
nu ii place ceva.  Eu pt ierarhia din exemplu  fac operatiile :

Cod:

1 1 1
1 2 4
1 3 3
1 5 3
1 3 3
1 1 1
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11

si obtin --->>>>

Cod:

-1
1 
-1
-1
-1
2 
-1
6 
-1
-1
5

   e ceva gresit aici ....poate observa cineva.

[Editat de bogdan2412: Use [ code ] cand vrei sa postezi cod / input / output files ]

[•bogdan2412]

Mie imi da

Cod:

-1
1
-1
-1
-1
2
-1
3
-1
-1
5

... Fa si tu pe foaie ca pot fi mai multe raspunsuri posibile pe acelasi query

[•tzipleatud]

Salut!

Cred ca ar trebui marita limita de timp la aceasta problema, deoarece am bagat solutia oficiala, cu O(sqrt N) pe update si pe query si iau doar 85 de puncte.  In plus, mi-am permis sa trimit o sursa care lua 100 in trecut, si acum ia doar 80 de puncte. ( Am vazut ca sunt surse de 100, cu arbori de intervale, dar nu stiu daca acelea au complexitatea optima worst-case).

Multumesc anticipat!

[•savim]

Ai dreptate, limita de timp era prea mica. Am crescut-o la 0.8s.

[•Sapientia]

"exista relatie directa intre angajatul p si angajatul q". -Sugereaza faptul ca p este "seful" lui q?

[•alexalghisi]

Nu chiar , faptul ca exista relatie directa intre p si q inseamna ca exista o muchie in arbore intre nodul p si nodul q.