Cod sursa(job #2720211)

Utilizator mihnea03Ciocioiu Mihnea mihnea03 Data 10 martie 2021 17:39:15
Problema Stramosi Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
#include <vector>
#define dim 250010
using namespace std;
vector<int> a[dim];
int d[dim][21];
int drum[dim];
int niv[dim];
int t[dim];
int f[dim];
int i,n,m,q,p,nod,e;

void dfs (int nod, int nivel) {
    f[nod]=1;
    niv[nod]=nivel;
    drum[nivel]=nod;
    for (int e=0;nivel-(1<<e)>=1;e++) {
        d[nod][e]=drum[nivel-(1<<e)];///d[nod][e]=ce nod se afla deasupra nodului curent cu 2^e nivele
    }

    for (auto vecin:a[nod]) {
        if (f[vecin]==0) {
            dfs(vecin,nivel+1);
        }
    }
}

int main() {
    ifstream fin("stramosi.in");
    ofstream fout("stramosi.out");
    fin>>n>>q;
    for (i=1;i<=n;i++) {
        fin>>t[i];
        if (t[i]==0) continue;
        a[i].push_back(t[i]);
        a[t[i]].push_back(i);
    }

    for (i=1;i<=n;i++) {
        if (t[i]==0) {
            dfs (i,1);
        }
    }

    for (;q--;) {
        fin>>nod>>p;///care este al p-lea stramos al lui nod
        p=niv[nod]-p;
        if (p<=0) {
            fout<<0<<"\n";
            continue;
        }
        e=18;
        while (nod!=p) {
            if (niv[nod]-(1<<e)<p) {
                e--;
            }
            else if (niv[nod]-(1<<e)>p) {
                nod=d[nod][e];
                e--;
            }
            else if (niv[nod]-(1<<e)==p) {
                nod=d[nod][e];
                break;
            }
        }
        fout<<nod<<"\n";
    }
    return 0;
}