1250 Markon

[•savim]

Aici puteti discuta despre problema Markon.

[•dorin31]

Ma puteti ajuta cu un hint, va rog? Nu pot sa-mi dau seama de ce nu trec de 20p..
Merci anticipat! 
http://www.infoarena.ro/job_detail/1693388?action=view-source

[•PlayLikeNeverB4]

Ce imi sare imediat in ochi e ca apelezi decreaseDegree de 2 ori pentru nodul initial. Apoi, cand ajungi la un nod, chiar daca nu indeplineste proprietatea 2, s-ar putea ca dupa ce treci de el sa o indeplineasca.

[•dorin31]

Am inteles, merci mult! 

[•tudorgalatan]

Cum pot scăpa de TLE?

Cod:

    NR = 1;
    sol[NR] = X;
    seen[X] = 1;
    for (w=1; w<=N*N*N*N; w++)
        for (i=1; i<=N; i++)
            if (!seen[i])
            {
                cnt1 = 0;
                AA = i;
                for (j=1; j<=A[AA][0]; j++)
                {
                    BB = A[AA][j];
                    if (seen[BB] == 1)
                    {
                        if (code[BB] == 0)
                            cnt1 = 1;
                        else
                        {
                            cnt2 = 0;
                            for (k=1; k<=A[AA][0]; k++)
                                if (seen[A[AA][k]] == 0)
                                    cnt2++;
                            if (code[BB] > cnt2)
                                cnt1 = 1;
                        }
                    }
                }
                if (cnt1 == 1)
                {
                    NR++;
                    sol[NR] = AA;
                    seen[AA] = 1;
                }
            }

[•PlayLikeNeverB4]

Nu e buna complexitatea. Verifica solutia oficiala.