Cod sursa(job #1945913)

Utilizator raduzxstefanescu radu raduzx Data 29 martie 2017 19:11:28
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <fstream>

using namespace std;
ifstream f("treap.in");
ofstream g("treap.out");
#define nmax 150010
struct nod
{
    int val;
    nod *urm;
};
typedef nod *pnod;
pnod p,v[nmax];
int n;
void ad(int x,int y)
{
    p=new nod;
    p->val=y;
    p->urm=v[x]->urm;
    v[x]->urm=p;
}
bool bun[nmax],use[nmax];
int t[nmax],st[nmax],heap[nmax],abc[nmax];
int first[nmax],last[nmax];
struct arbc
{
    int val;
    arbc *as,*ad;
};
typedef arbc *parbc;
int to=0;
void bfs(int inc)
{
    pnod p;
    p=v[inc]->urm;
    use[inc]=1;
    to+=1;
    first[inc]=to;
    while(p)
    {
        if(use[p->val]==0)
        {
            v[p->val]->val-=1;
            t[p->val]=inc;
            bfs(p->val);
        }
        p=p->urm;
    }
    to+=1;
    last[inc]=to;
}
int cresc[nmax];
void bunheap()
{
    int i;
    for(i=1;i<=n;i++)
    {
        if(bun[i]==1)
        {
            p=v[i]->urm;
            if(p)
            {
                if(t[i]!=p->val and heap[i]<heap[p->val])
                    bun[i]=0;
                if(p->urm and t[i]!=p->urm->val and heap[i]<heap[p->urm->val])
                    bun[i]=0;
            }
        }
    }
}
parbc creeaza(int rad)
{
    pnod p;
    p=v[rad]->urm;
    int a=0,b=0;
    parbc ass=0,add=0,w,q;
    while(p)
    {
        if(t[rad]!=p->val)
        {
            w=creeaza(p->val);
            if(a)
            {
                b=p->val;
                add=w;
            }
            else
            {
                a=p->val;
                ass=w;
            }
        }
        p=p->urm;
    }
    q=new arbc;
    q->val=rad;
    q->as=ass;
    q->ad=add;
    return q;
}
void srd(parbc rad)
{
    if(rad)
    {
        srd(rad->as);
        to+=1;
        cresc[to]=abc[rad->val];
        srd(rad->ad);
    }
}
int main()
{
    parbc rad;
    int i,x,y,j;
    f>>n;
    for(i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->urm=0;
        v[i]->val=0;
        bun[i]=1;
    }
    for(i=1;i<n;i++)
    {
        f>>x>>y;
        ad(x,y);
        ad(y,x);
        v[x]->val+=1;
        v[y]->val+=1;
    }
    for(i=1;i<=n;i++)
    {
        f>>abc[i];
    }
    for(i=1;i<=n;i++)
    {
        f>>heap[i];
    }
    bfs(1);
    for(i=1;i<=n;i++)
    {
        if(v[i]->val>2)
            bun[i]=0;
    }
    bunheap();
    rad=creeaza(1);
    to=0;
    srd(rad);
    for(i=2;i<=n;i++)
    {
        if(cresc[i-1]>cresc[i])
        {
            if(first[i-1]<first[i] and last[i]<last[i-1])
            {
                bun[t[i]]=0;
            }
            else
                bun[t[i-1]]=0;
        }
    }
    for(i=2;i<=n;i++)
    {
        if(bun[i]==0)
        {
            j=t[i];
            while(j and bun[j]==1)
            {
                bun[j]=0;
                j=t[j];
            }
        }
    }
    for(i=1;i<=n;i++)
        g<<bun[i]<<" ";
    return 0;
}