Nu stiu exact in ce consta acea librarie, insa cu siguranta poate fi paralelizat deoarece fiecare subproblema poate fi rezolvata independent...

Parcurgem sirul si pentru fiecare element x, verificam daca x - 1 si/sau x + 1 au fost intalnite anterior(cu un hash). Daca ambele au fost, atunci inseram una dintre multimi in cealalta(multimea lui X= {multimea maximala de numere consecutive intalnite inaintea lui X}  U  {X} ), inclusiv pe x(cu multimi disjuncte), daca doar una din valori a fost intalnita anterior il inseram pe x in acea multime.

Da. Faci o structura asa:
struct compare{
   bool operator  < (tip a, tip b) const{
       return a < b;//poti compara cum vrei aici
   }
}
iar cand sortezi apelezi asa : sort(a.begin(), a.end(), compare());

Iar daca "tip" este la randul sau o structura poti supraincarca operatorul < astfel:
bool operator < (tip a) const{
    return this->x < a.x;//La fel , poti sorta cum vrei
}
...
sort(a.begin(), a.end());//fara alti parametrii

Am rezolvat problema cu 3 df-uri.
1) caut lungimea drumului maxim
2) fac dinamica: dp[ i ] numarul de drumuri de lungime maxima ce pornesc din nodul i
3) caut al k-lea drum

Folosesc 52 de set-uri in loc de matrice, probabil de aici mi se trage TLE (desi 2500 muchii nu mi se par multe). Problema e ca iau si WA, desi pe testele mele merge Any help?

Sa zicem ca suma fixata este S. Pentru a afla cate sume sunt mai mici ca aceasta, pentru fiecare element din vector trebuie sa vedem cate elemente din acelasi vector sunt mai mici sau egale cu S - element_curent si cate sunt strict  mai mici decat S - element_curent. Sumele acestor valori sa le notam cu upper si lower. Tot ce mai trebuie facut este sa verificam daca lower < k && k <= upper.

1 , 11 , 12

Cam aceeasi complexitate se obtine si cu LCA pentru constructie, apoi O(1) pe query. Verificam daca LCA dintre X si Y este nodul Y.
LE: Si cum zice cosmin se poate face LCA. Eu ma refeream la RMQ

Pentru un query=0 ce-ti afiseaza? Si din cate tin minte trebuie lucrat pe long long

Ce nu ar fi bine in ideea asta:
Caut timpul binar(diferenta maxima minima dintre plecare si sosire) ,fac un dijkstra . Pentru fiecare nod pe care-l scot din coada(fie it o muchie care iese din nod)

daca trece de codul urmator relaxez muchia si sosire[it->y]=it->sosire;

Cod:

if(nod==1)
        sosire[nod]=it->plecare;
			
if(sosire[nod]>it->plecare)
	continue;
			
if(dif < it->plecare-sosire[nod])
	continue;
			
if(cost[it->y] <= cost[nod]+it->cost)
	continue;

Muchiile le retin exact cum se dau in fisierul de intrare.

Este exagerata limita de timp, din cate am vazut intra mai bine o coada simpla decat un heap.

Exista intotdeauna solutie? Pentru un exemplu ca asta:
5 4 2 3
1 5
5 1
1 2
2 3
3 4

Raspunsul este 5 ?(1->2 ; 5->4)

Tocmai m-am lovit si eu de problema asta. In functie de cum gaseste fluxul, solutia poate fi buna sau nu ....  
Probabil trebuie facui fluxul intr-un anume fel 

Eu nu stiu cum puteti sa ziceti sa se anuleze sursele dupa 5 h... Dupa ce ca a inceput mai tarziu au mai fost si problemele astea cu siteul. Eu jumate din timp am stat sa dau refresh ca sa reusesc sa-mi pun sursele Problemele au fost frumoase, dar nu se poate face nimic ca siteul sa mearga mai bine?

Dupa parerea mea testele nu sunt foarte bune. Eu daca am permutarea 1200...00 (3 milioane de zerouri sa zicem) , o sa pastrez tot sirul in memorie... si iau 100 asa.

Ca sa faci heap sortul stabil trebuie sa retii si pozitiile pentru fiecare nod, deci ai o(n) memorie suplimentara. Probabil e alta idee.
LE: sau bagam un stable_sort

Stable_sort is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available. Worst-case behavior (if no auxiliary memory is available) is N (log N)^2 comparisons, where N is last - first, and best case (if a large enough auxiliary memory buffer is available) is N (log N)

sau

Inplace_merge is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available. Inplace_merge performs no comparisons if [first, last) is an empty range. Otherwise, worst-case behavior (if no auxiliary memory is available) is O(N log(N)), where N is last - first, and best case (if a large enough auxiliary memory buffer is available) is at most (last - first) - 1 comparisons.

Implementarile sunt in headerul algorithm.

Daca soldatul 1,care e initial pe pozitia 2,se deplaseaza pe pozitia 4 apoi pe 5, se afiseaza
M 1 4
M 1 5

sau direct
 M 1 5
?
Nu inteleg la ce se refera (fara a se preciza pozitiile intermediare) .

Daca fac belman ford cu coada numarand sa nu am mai mult de n*m pasi si apoi verific daca pentru muchiile existente se poate obtine un cost mai mic nu e corect? Iau 0 puncte cu abordarea asta pe cand cu un belman ford fara coada aplicat de n ori si apoi verificarea iau 60.

Zici ca daca vectorul e gol si tu apelezi .size() iti da eroarea aia? Daca e gol .size()=0,nu-ti da eroare

Daca prima si cea de-a k scandura sunt lipsa raspunsul este 0?

Frumos Hai ca o sa ma apuc sa scriu. Intre timp am facut un fel de atan2 de mana =)) dar iau 2 WA. Creca omit vreun caz.

Cod:

inline bool cmp(p a,p b)
{
	ld adx=a.first-fix.first;
	ld ady=a.second-fix.second;
	ld bdx=b.first-fix.first;
	ld bdy=b.second-fix.second;
	//1
	if(adx>=0&&ady>=0)
	{
		if(bdx==0&&bdy>0)
			return 1;
		if(bdx==0&&bdy<0)
			return 0;
		if(bdx>0&&bdy==0)
			return 0;
		if(bdx<0&&bdy==0)
			return 0;
		if(bdx>0&&bdy>0)
		{
			if(adx==0)
				return 0;
			if(ady==0)
				return 1;
			return (ld)ady/adx<(ld)bdy/bdx;//1
		}
		if(bdx<0&&bdy>0)
			return 1;
		else
			return 0;
	}
	//2
	if(adx<=0&&ady>=0)
	{
		if(bdx<0&&bdy>0)
			return (ld)ady/adx<(ld)bdy/bdx;//2
		else
			return 0;//1 3 4
	}
	//3
	if(adx<=0&&ady<=0)
	{
		if(ady==0&&adx<0)
			return 1;//1 2 4
		if(bdx<0&&bdy<0)
			return (ld)ady/adx<(ld)bdy/bdx;//3
		else
			return 1;//1 2 4
	}
	//4
	if(adx>=0&&ady<=0)
	{
		if(bdx==0&&bdy>0)
			return 1;
		if(bdx==0&&bdy<0)
			return 0;
		if(bdx>0&&bdy==0)
			return 1;
		if(bdx<0&&bdy==0)
			return 0;
		if(bdx>=0&&bdy<=0)
		{
			if(adx==0)
				return 1;
			if(ady==0)
				return 0;
			return (ld)ady/adx<(ld)bdy/bdx;
		}
		if(bdx<0&&bdy<0)
			return 0;
		else
			return 1;
	}
}

L.E.  A mers   O sa tin minte treaba asta. MS  

Se poate imbunatatii cumva timpul functiei atan2? Sau mai exista vreo metoda asemanatoare?
Vreau sa sortez punctele in jurul closcai

A rezolvat-o cineva  cu Rabin-Karp?

Mai precis?
Impartirea lui P la fiecare factor prim (de putere_factor ori) iese din timp...

Sti ca numarul ala foarte mare e format astfel n*(n+1)*(n+2)*...*(n+m) unde 1<=n<=n+m<=100000 deci sti ca factorii primi sunt mai mici ca 100000 si astfel poti logaritma numarul ala mare

Daca am de exemplu sirurile :

cse adcse se

si vreau sa vad care din ele este sufix pentru abadcse. Dupa ce formez numarul lui abadcse cu rabin karp, incerc sa scap de cate o litera de la inceput folosind aceeasi schema ca si la potrivire de siruri dar fara sa mai inmultesc cu baza si sa adun alt element.
sir3=(sir3-(c[j]*Pow1)%MOD1+MOD1)%MOD1
Nu e buna solutia sau gresesc eu ceva?