Am gasit o explicatie foarte buna aici: http://stackoverflow.com/questions/16250337/about-tarjans-algorithm-for-finding-scc.
Implementarea pe care ai dat-o e interesanta pentru ca nu verifica daca nodul e in stiva cand ia minimul, de ce functioneaza?

Mi se pare ca solutia oficiala care implementeaza algoritmul lui Tarjan nu e chiar corecta. Cel putin in cazul doi cand avem o muchie inapoi,

Cod:

low[node] = min(low[node], idx[new_node]); 
si nu 
low[node] = min(low[node], low[new_node]); 

intrucat low[node] ar trebui sa fie indicele minim pe care il putem atinge printr-o singura muchie inapoi.
Asa vad ca e implementat pe wikipedia, iar in articolul asta chiar insista pe aceasta greseala.
Sunt curios daca ar trebui imbunatatite testele sau pur si simplu modificarea asta nu afecteaza neaparat corectitudinea algoritmului.

ni ba , daca tot pica inainte de bac algoritmiada r 3 rog propunatorii de probleme sa creeze enunturi care au legatura cu operele de bac
 (enigma otiliei, morometii , floare albastra , plumb , sau ultima noapte ) poate asa o sa trec si eu multumiri .

Sustin!

Cod:

Explicaţie
Colonia 1 depinde de colonia 3.

Colonia 1 nu depine cumva de colonia 2?

L.E. E okay, credeam ca C = 1, imi cer scuze.

Asta e asa, ca de 1 Aprilie?

Imi poate explica cineva cum se poate folosi algoritmul de flux la problema Naveplanare? Nu pot sa-mi dau seama cum arata reteaua. Multumesc anticipat !

Pentru exemplul 2, query-ul 2, raspunsul corect nu e 32.5?

Se va posta si articolul cu solutii ? 

Chiar asa, as fi si eu foarte curios de solutia la Kthvalue.

Cand va fi postat articolul cu solutiile:)?

Si daca ai mesajul ok nu iti dai seama ca ai trecut testul )?

Sunt curios cum suna solutia oficiala la Disconnect, fara structuri de date .

Cata memorie avem pentru stiva?

imi poate spune cineva ce greseala este in codu:
 
#include<iostream.h>
#include<fstream.h>
using namespace std;
 
int a,b;
int main()
{
    ifstream f("adunare.in");
    ofstream g("adunare.out");
    f>>a;
    f>>b;
    g<<a+b;
     
    f.close();
    g.close();
    return 0;
}

Librariile trebuie fara extensia .h, sunt deprecated. Scoate .h si o sa iti mearga .

http://www.spoj.com/problems/KPARCH/

Imi dati si mie o idee cum as putea folosi Suffix Arrays in problema asta? La comentarii se mentioneaza si despre 'extended KMP', oare la ce se refera (pe google nu am gasit nimic despre asa ceva) ?

Depinde de implementare, mie mi-a intrat cu Treap-uri folosind stream-uri.
Linia asta e magica:

Cod:

cin.sync_with_stdio(false);

Salutare !

Am si eu o interbare: Cum ar fi algoritmul de flux pentru un graf neorientat ?

Multumesc anticipat.

Salut!
Sebi are dreptate, practic cand iti construiesti graful pui capacitate C si pe muchia y -> x, nu doar pe x -> y.
Ar mai fi o idee destul de inteligenta si anume fiecare nod x il transformi in doua noduri, fie ele x1 si x2, astfel ca in x1 vor intra toate muchiile incidente in x si din x2 vor iesi toate muchile care ies din x (iar intre x1 si x2 ai capacitate infinita). Mai exact pentru o muchie neorientata x-y o sa bagi in graful tau urmatoarele muchii orientate: x2 -> y1 si y2 -> x1. Si astfel am redus problema la flux maxim intr-un graf orientat.

Raspunsul incape pe int sau long long?

Incepand cu runda aceasta problemele vor fi sortate dupa dificultate?

Cu sursa de 100 mie imi da:

Cod:

7

Buna!

Am rezolvat problema Atac2 care se bazeaza pe cuplaj maxim de cost minim si initial luam 60 de puncte fiindca pentru o muchie x -> y nu adaugam costul -z muchiei y -> x. Poate sa imi explice cineva de ce se introduce acea muchie de cost invers?

La problema alegeri am incercat urmatoarea idee . Luam muchiile din graful initial,  pe muchiile bune puneam cost 0 iar pe cele stricate puneam costul pe care il citeam . Apoi construiam APM-ul pentru graful acesta si afisam valoarea. In cazul in care nu puteam construi APM-u , (graful nu era conex) afisam -1. Ce e gresit la abordarea asta ?

Pe aceeasi idee am luat 100, probabil e de la implementare. Ai grija sa resetezi vectorii si multimile disjuncte (daca faci Kruskal).

Vedeti ca e gresita explicatia primului test. In explicatie raspunsul e 600 si in fisierul de iesire e 570...

L.E: Emisiunile se dau sortate dupa ora inceperii?

Felicitari tuturor participantilor si mult succes celor calificati in pregatirea pentru ONI  .

Daca prin reference te referi la documentatia C++, atunci trebuie sa stii ca la oji ar trebui sa ai un fisier pe Desktop numit  C++ Reference.
Poti descarca acelasi fisier de aici. Nu e neaparat sa instalezi tot OJI Kit, bifezi doar documentatia.

In 9 e mai ok ca in 8 e judeteana la mate...