Cod sursa(job #1649206)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 11 martie 2016 12:49:33
Problema Stramosi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#define nmax 250010
using namespace std;

int n,m1,np;
int dad[nmax];
int nrp[nmax];
int pater[nmax][20];
vector<int> m[nmax];

void dfs(int nod)
{
    for(vector<int>::iterator it=m[nod].begin();it!=m[nod].end();it++)
    {
        nrp[*it]=nrp[nod]+1;
        pater[*it][0]=dad[*it];
        for(int i=0; (1<<i)<=nrp[*it]; i++);
         //   pater[ *it ][ (1<<i) ]=pater[ pater[ *it ][ (1<<i)-1 ] ][ (1<<i)-1 ];
        dfs(*it);
    }
}

int finds(int k,int nod)
{
    int i;
    for(i=0;(1<<i)<=k;i++); i--;
    if( (1<<i) == k ) return pater[nod][i];
    return finds( k-(1<<i),pater[nod][i] );

}

int main()
{
    int nod,i,j,who,nr;
    freopen("stramosi.in","r",stdin);
    freopen("stramosi.out","w",stdout);
    scanf("%d%d",&n,&m1);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&dad[i]);
        m[ dad[i] ].push_back(i);
    }
    nrp[0]=-1;
    dfs(0);

    /*for(;m1;m1--)
    {
        scanf("%d%d",&who,&nr);
        if( nr>nrp[who] ) printf("0\n");
        else printf("%d\n",finds(nr,who));
    }*/

    fclose(stdin);
    fclose(stdout);
    return 0;
}