1126 Dominouri

[•andrei.12]

Aici puteti discuta despre problema Dominouri.

[•horatiu11]

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  ?

[•thewildnath]

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  ?

 
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