subscriu ca se poate lua 100 cu un bkt optimizat.

a luat cineva 100p cu un program de complexitate n+m*p?
Pentru fiecare query caut stramosul cu ceva de genul x = tata [ x ]; (pentru asta am luat 80 p cu TLE pe ultimele 2)
Am incercat si sa imi 'preprocesez' al p-lea stramos pentru fiecare om si am luat memory limited exceeded pe ultimele 4 teste

@vlad eugen: punctul urmator il alegi in functie de sensul lui trigonometric in raport cu ultimele 2 puncte din infasuratoare. Si sensul trigonometric se calculeaza cu determinanti (cred ca asta nu ai inteles tu din functiile respective).
Sensul a 3 puncte (a,b,c) este calculat prin urmatorul determinant:
|a.x a.y 1|
|b.x b.y 1| = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y)
|c.x c.y 1|
Daca e mai mare decat 0 punctele sunt intr un sens si daca e mai mic decat 0 sunt in celalalt sens (nici eu nu stiu exact care sens e care dar cu o foaie in mana afli repede); daca determinantul e 0 atunci punctele sunt coliniare.

Tip pentru viitor: abs(determinantul de mai sus) reprezinta dublul ariei acelui triunghi.

Acum am si eu o intrebare: stie cineva cum functioneaza setprecision. Momentan am cos 100 de puncte cu setprecision(20) dar nu stiu exact ce inseamna 20-ul ala

se poate lua 100 pe problema si fara cautare binara (sau testele nu sunt indeajuns de stricte), folosind o matrice in care in v [ x ] [ y ] se tine minte valoarea minim de pe drumul pana in punctul de coordonate x si y

testul ala im merge

Si apropo de teste care nu au domino cu 1 si eu greseam asta, dar am rezolvat.

Tot la 80 am ramas

1) stie cineva vre-un test mai special? [cazul cu 0 imi merge sigur]

2) am o parcurcere in adancime (pana sunt folosite toate piesele) pe o matrice de adiacenta de 10/10; ce pot sa mai optimizez sa nu iau TLE?

3) cam in ce complexitate e functia din stl v.size() (unde v = vector)

prin STL cred ca depinde de implementare si de mici optimizari.. de exemplu stiu ca cineva a luat 100 dupa ce a micsorat dimensiunea vectorilor cu 1 sau 2

btw.. eu inca sunt uimit ca functioneaza: job #482680 si are si un timp foarte bun. pe testul pe care luam TLE fac acum 52 ms (sursa mea: job #557996 )