Imprimă pagina - 1126 Dominouri

Am incercat sa fac problema asta cu un dfs din nodul 1 si cu o sortare pe nivel in dfs. Pe testele mele imi da ok dupa parerea mea. Insa pe evaluator iau 0 puncte cu multe incorect si cateva killed by signal 11. Cei care ati facut problema, puteti sa ma ajutati cu sursa asta
http://www.infoarena.ro/job_detail/1083183?action=view-source ?

Citat din mesajul lui: Ilie Ovidiu Horatiu din Ianuarie 16, 2014, 06:32:21

Si eu am aplicat ideea aceasta si am luat 100.
Eu am facut functia DFS de tip int si DFS(nod) returneaza numarul minim de dominouri care trebuie daramate pentru ca nodul 'nod' sa cada.

Incearca in loc de

Cod:

inline void dfs(int x)
{
    int i,v[nmax],L=0;
    viz[x]=true;
    for(i=0;i<G[x].size();++i)
        if(!viz[G[x][i]])
        {
            dfs(G[x][i]);
            v[++L]=a[G[x][i]];
        }
    sort(v+1,v+L+1);
    int s=0;
    for(i=1;i<=a[x];++i)
        s+=v[i];
    F[x]=max(F[x],s);
}

sa faci:

Cod:

int dfs(int x)
{
    if(!F[x])
        return 1;
    
    int i,v[nmax],L=0;
    for(i=0;i<G[x].size();++i)
        v[++L]= dfs(G[x][i]);
    
    sort(v+1,v+L+1);
    int s=0;
    for(i=1;i<=L && F[x];++i,--F[x])
        s+=v[i];
    return s;
}

Sper sa te ajute :D

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Andrei Parvu din Aprilie 10, 2011, 10:51:47