975 Arbore3

[•pauldb]

Aici puteti discuta despre problema Arbore3.

[•a_h1926]

As avea si eu o intrebare. Am folosit o tabela de hash in care inserez costurile drumurilor de la radacina (nodul 1) la nodul curent (pe care le inserez pe masura ce fac un DFS), iar inainte sa revin din apelul recursiv al unui DFS, sterg din hash valoarea drumului curent, iar la fiecare pas verific daca exista in hash valoarea drumului curent-S (daca da, inseamna ca exista unul sau mai multe drumuri mai mici pe care daca le exclud din drumul curent voi obtine un drum cu costul S si incrementez solutia cu numarul de aparitii al acelei valori). Totusi, iau 0 puncte, pe 3 teste primesc "Killed by signal 6(SIGABRT).", si pe celelalte 7 primesc "Killed by signal 11(SIGSEGV).". Chiar nu stiu ce poate avea, am reprezentat arborele si hash-ul folosind vectorii din STL. Nu mai stiu ce sa fac, voi posta sursa aici si daca binevoieste cineva sa se uite peste ea, m-as bucura foarte mult. Multumesc anticipat.

Cod:

#include <iostream>
#include <cstdio>
#include <vector>

#define NMax 1000005
#define U 666013

using namespace std;

vector <int> A[NMax];
vector <int> HT[U+5];
int N, Value[NMax], S, NRoads;

void Read ()
{
    freopen ("arbore3.in", "r", stdin);
    scanf ("%d %d", &N, &S);
    for (int i=1; i<=N; ++i)
    {
        int F;
        scanf ("%d %d", &F, &Value[i]);
        A[F].push_back (i);
    }
}

void Print ()
{
    freopen ("arbore3.out", "w", stdout);
    printf ("%d\n", NRoads);
}

int Search (int X)
{
    int Key=X%U, NX=0;
    for (unsigned i=0; i<HT[Key].size (); ++i)
    {
        if (HT[Key][i]==X)
        {
            ++NX;
        }
    }
    return NX;
}

void Insert (int X)
{
    int Key=X%U;
    HT[Key].push_back (X);
}

void Delete (int X)
{
    int Key=X%U;
    if (HT[Key].size ()==0)
    {
        return;
    }
    for (vector <int> :: iterator H=HT[Key].begin (); H!=HT[Key].end (); ++H)
    {
        if (*H==X)
        {
            HT[Key].erase (H);
            return;
        }
    }
}

void DFS (int X, int Cost)
{
    int C=Cost+Value[X];
    NRoads+=Search (C-S);
    Insert (C);
    for (unsigned V=0; V<A[X].size (); ++V)
    {
        DFS (A[X][V], C);
    }
    Delete (C);
}

int main()
{
    Read ();
    Insert (0);
    DFS (1, 0);
    Print ();
    return 0;
}

[•PlayLikeNeverB4]

Vezi ca valoarea sumei de la radacina la un nod poate fi si negativa.

[•dutzul]

Hmm prima data cand am trimis sursa am folosit functia de hash %666013 am luat 30 de pcte
apoi am setat pe 66013 --60 de pcte
apoi 6013 --- 80-90
hmm nu ar trebui sa fie oarecum invers?

[•danalex97]

Am patit si eu chestia asta la alte probleme si sunt si eu curios care e explicatia.   Si as mai avea si eu o intrebare... Am gasit intr-o sursa de la problema muzica un hash implementat cu STL din headerul <tr1/unordered_map>. Am citit pe wikipedia ca tr1 este un fel de extensie a STL-ului. Sunt curios daca compilatoarele de la ONI accepta acest header. Poate e o intrebare putin prosteasca , dar nu stiu mai nimic despre compilatoare sau cum se evalueaza problemele   ...

[•PlayLikeNeverB4]

De obicei daca declari mai multa memorie ii ia mai mult timp sa o aloce. Posibil ca de asta luai TLE.

[•repp4radu]

Am patit si eu chestia asta la alte probleme si sunt si eu curios care e explicatia.   Si as mai avea si eu o intrebare... Am gasit intr-o sursa de la problema muzica un hash implementat cu STL din headerul <tr1/unordered_map>. Am citit pe wikipedia ca tr1 este un fel de extensie a STL-ului. Sunt curios daca compilatoarele de la ONI accepta acest header. Poate e o intrebare putin prosteasca , dar nu stiu mai nimic despre compilatoare sau cum se evalueaza problemele   ...

Din ce scrie pe aici unordered_map este introdus in ultima actualizare a standardului C++, insa nu stiu daca se va face actualizarea compilatoarelor de la OJI/ONI astfel incat sa fie suportat ca apartinand standardului.
Oricum, daca folosesti tr1 in fata ar trebui sa mearga(cred) 

[•danalex97]

Multumesc. E bine de stiut. 

[•superman_01]

Buna..am si o problema tot incerc problema si nu imi dau seama ce as putea sa optimizez pentru a lua 100.Ati putea sa va uitati si sa imi ziceti ce sa optimizez?

[•PlayLikeNeverB4]

Mareste hashul.

[•superman_01]

l-am marit ,dar tot 90 cu timpi chiar mai mari...nu cred ca e aia tinand cont ca ii ia mai mult sa aloce  memorie cum ziceai mai sus si atunci de aia sa iau TLE .