Cod sursa(job #1201666)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 25 iunie 2014 18:28:30
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

#define pb push_back

using namespace std;
int N,nivmax;
struct Arb{int st,dr,niv,fs,fd,pz;}G[1005],cate[1005];
vector<int> nivel[1005];
int spart[1005];

void read()
{
    scanf("%d",&N);
    int a,b,c;
    for(int i = 1; i <= N; ++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        G[a].st = b;
        G[a].dr = c;
    }
}

void BFS()
{
    int nodc,latmax = 1,nivlatmax = 1,niv = 1,lat;
    queue<int> Q,aux;
    Q.push(1);
    nivel[1] .pb(1);
    spart[1] = 1;
    while(!Q.empty())
    {
        ++niv;
        nivmax = niv;
        lat = 0;
        while(!Q.empty())
        {
                nodc = Q.front();Q.pop();
                if(G[nodc].st != -1)
                {
                    aux.push(G[nodc].st),++lat;
                    nivel[niv].pb(G[nodc].st);
                }
                if(G[nodc].dr != -1)
                {
                    aux.push(G[nodc].dr),++lat;
                    nivel[niv].pb(G[nodc].dr);
                }
        }
        spart[niv] = spart[niv-1]+lat;
        while(!aux.empty())
            Q.push(aux.front()),aux.pop();
        if(lat > latmax)
            latmax = lat,nivlatmax = niv;
    }

}

void DFS(int k,int st,int dr,int niv)
{
    //printf("%d ",k);
    G[k].niv = niv;

    if(G[k].st != -1)
    {
        DFS(G[k].st,st+1,dr,niv+1);
        G[k].fs = G[G[k].st].fs + G[G[k].st].fd + 1;
    }
    if(G[k].dr != -1)
    {

        DFS(G[k].dr,st,dr+1,niv+1);
        G[k].fd = G[G[k].dr].fs + G[G[k].dr].fd + 1;
    }
    if(G[k].dr + G[k].st == -2)
    {
        G[k].fs = 0;
        G[k].fd = 0;
    }
}

void parcurge(int k)
{
    if(G[k].st != -1)
    {
        G[G[k].st].pz = G[k].pz - (G[G[k].st].fd ) - 1;
        parcurge(G[k].st);
    }
    if(G[k].dr != -1)
    {
        G[G[k].dr].pz = G[k].pz + (G[G[k].dr].fs + 1);
        parcurge(G[k].dr);

    }
}

void solve()
{
    int latus = 0,Lmax=1,nLmax=1;
    for(int i = 2;i < nivmax; ++i)
    {
        latus = G[nivel[i][nivel[i].size()-1]].pz - G[nivel[i][0]].pz +1;
        if(latus > Lmax)
        {
            Lmax = latus;
            nLmax = i;
        }
    }
    printf("%d %d\n",nLmax,Lmax);
}

bool cmp(int a,int b)
{
    return G[a].pz < G[b].pz;
}

void mai_fa()
{
    for(int i = 1; i <= nivmax; ++i)
        sort(nivel[i].begin(),nivel[i].end(),cmp);
}

int main()
{
    freopen("latime.in","r",stdin);
    freopen("latime.out","w",stdout);

    read();
    BFS();
    DFS(1,0,0,1);
    G[1].pz = G[1].fs + 1;
    parcurge(1);
    mai_fa();
    solve();

    return 0;
}