Porodicno stablo - A2 2014

Pitanja i problemi
1

Moze mala pomoc oko ovog zadatka?

2

Jedan DFS obilazak.

Imas 2 promenljive - lo i hi, gde je lo maksimalan broj koji se moze dobiti tako da je lo <= trazenog, hi minimalan tako da hi >= trazenog.

Neka je dp[i] broj nacina na koji mozes dobiti broj i na putu od korena do cvora u kojem si trenutno (x).

for(int i = s; i >= 0; i–)
{
int j = i + a[x];
if(!d[i]) continue;
if(j > s) hi = min(hi, j);
else if(j <= s)
{
lo = max(lo, j);
d[j] += d[i];
}
}
E sad rekurzivno pozoves za sinove, ali ne smes zaboraviti da se “vratis” i da posle ispitivanja puta od cvora i do nekog lista obrises ono sto si dodavao u dp niz (ometace ostatak procesa, tj. put od cvora i pa do nekog drugog lista).
for(int i = a[x]; i <= s; i++)
{
int j = i - a[x];
if(!d[j]) continue;
d[i] -= d[j];
}

Ovo resenje mi radi za prva 4 test primera ali daje MLE na ostalima, sto ne znaci da je zaista MLE (Problem sa zad Porodicno stablo (DrĹľavno 2014 SĹ  - A2))

3

Proverio sam da li zapravo postoji problem sa memorijom tako sto sam submitovao neki od kodova koji je prolazio na takmicenju i na moje iznenadjenje prosao je bez problema.

4

Kako? Kada ucitavam input sa samo 4 varijable dobijem MLE? Uostalom, jel mozes postaviti taj kod?

5 
#include <cstdio>
#include <algorithm>

using namespace std;

short son[10005];
short ep[10005],ek[10005];
short dif[10005];

int n,s;
int val[10005];
char notrut[10005];

inline bool komp(int a,int b)
{
    return dif[a]<dif[b];
}

inline void setdif(int u)
{
    for (int i=ep[u]; i<ek[u]; i++)
        setdif(son[i]);
    sort(son+ep[u],son+ek[u],komp);
    if (ep[u]==ek[u])
    {
        dif[u]=1;
        return;
    }
    if (ep[u]+1==ek[u])
    {
        dif[u]=dif[son[ep[u]]];
        return;
    }
    dif[u]=max(dif[son[ek[u]-1]],(short)(dif[son[ek[u]-2]]+1));
}

int nodes[40][315];
int cnode;

int best;
inline int aps(int a)
{
    if (a<0)
        return -a;
    return a;
}
inline void uporedi(int val)
{
    if (aps(s-best)>aps(s-val) || (aps(s-best)==aps(s-val) && val<best))
        best=val;
}
inline void skinicvor()
{
    for (int i=0; i<315; i++)
        nodes[cnode-1][i]=nodes[cnode][i];
    cnode--;
}
inline void napravicvor(int val)
{
    for (int i=0; i<315; i++)
        nodes[cnode+1][i]=nodes[cnode][i];
    cnode++;
    for (int i=s-1; i>=0; i--)
        if (nodes[cnode][i>>5]&(1<<(i&31)))
        {
            uporedi(i+val);
            if (i+val<=s)
                nodes[cnode][i+val>>5]|=1<<(i+val&31);
        }
}

inline void resi(int u)
{
    char del=0;
    while (ep[u]<ek[u])
    {
        int v=son[ep[u]];
        napravicvor(val[v]);
        ep[u]++;
        if (ep[u]==ek[u])
        {
            del=1;
            skinicvor();
        }
        resi(v);
    }
    if (del==0)
        cnode--;
}

int main()
{
    scanf("%d%d",&n,&s);
    int cdg=1;
    for (int i=1; i<=n; i++)
    {
        scanf("%d",&val[i]);
        int deg;
        scanf("%d",&deg);
        ep[i]=cdg;
        ek[i]=ep[i]+deg;
        cdg+=deg;
        for (int j=ep[i]; j<ek[i]; j++)
        {
            scanf("%d",&son[j]);
            notrut[son[j]]=1;
        }
    }
    int rut=-1;
    for (int i=1; i<=n; i++)
        if (notrut[i]==0)
            rut=i;
    setdif(rut);
    cnode=1;
    nodes[1][0]=1;
    napravicvor(val[rut]);
    resi(rut);
    printf("%d\n",best);
}

Evo ga kod.U prva dva reda treba ukljuciti biblioteke cstdio i algorithm ali se ne vide dobro.

6

@igzi Mozes da koristis formatiranje koda, znak </>

7

Zaista nema problema sa memorijom, prosao je sada i moj kod sa sledecim izmenama:
Umesto <bits/stdc++.h> sam stavio cstdio i algorithm, i umesto void dfs(int x) - inline void dfs(int x)

8

Memorijsko ogranicenje za taj zadatak je previse nisko, treba da bude vise. Moguce je da dosta tacnih resenja ne prolazi.

1 Like
9

Izgleda da je to ogranicenje ispravno :slight_smile: