Cod sursa(job #2788069)

Utilizator Matei_PanzariuMatei Panzariu Matei_Panzariu Data 24 octombrie 2021 20:57:34
Problema Lowest Common Ancestor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream cin("lca.in");
ofstream cout("lca.out");
vector<int>mu[100002];
int n,q,x,f[100002],v[100002],k,level[100002],app[100002],rmq[100002][22];
void DFS(int x,int l)
{
    f[x]++;
    v[++k]=x;
    if(app[x]==0)
        app[x]=k;
    level[k]=l;
    for(int i=0; i<mu[x].size(); i++)
        if(f[mu[x][i]]==0)
        {
            DFS(mu[x][i],l+1);
            v[++k]=x;
            level[k]=l;
        }
}
int main()
{
    cin>>n>>q;
    for(int i=2; i<=n; i++)
    {
        cin>>x;
        mu[i].emplace_back(x);
        mu[x].emplace_back(i);
    }
    DFS(1,0);
    for(int i=1; i<=k; i++)
        rmq[i][0]=i;
    ///RMQ
    for(int lg=2,exp=1; lg<=k; lg*=2,exp++)
        for(int i=1; i+lg<=k; i++)
        {
            if(level[rmq[i][exp-1]]>level[rmq[i+lg/2][exp-1]])
                rmq[i][exp]=rmq[i+lg/2][exp-1];
            else
                rmq[i][exp]=rmq[i][exp-1];
        }
    for(int i=1; i<=q; i++)
    {
        int x,y;
        cin>>x>>y;
        x=app[x];
        y=app[y];
        if(x>y)
            swap(x,y);
        int lg=y-x+1;
        int p=1;
        int exp=0;
        while(p<=lg)
        {
            p*=2;
            exp++;
        }
        p/=2;
        exp--;
        if(level[rmq[x][exp]]>level[rmq[y-p+1][exp]])
            cout<<v[rmq[y-p+1][exp]]<<'\n';
        else
            cout<<v[rmq[x][exp]]<<'\n';
    }
    for(int i=1; i<=k; i++)
    {
        for(int j=0; j<=k/2; j++)
            cout<<rmq[i][j]<<' ';
        cout<<'\n';
    }
    for(int i=1; i<=k; i++)
        cout<<v[i]<<' ';
    cout<<'\n';
    for(int i=1; i<=k; i++)
        cout<<level[i]<<' ';
    cout<<'\n';
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<mu[i].size(); j++)
            cout<<mu[i][j]<<' ';
        cout<<'\n';
    }
    for(int i=1; i<=n; i++)
        cout<<app[i]<<' ';
}