Submission #475595

#	Time	Username	Problem	Language	Result	Execution time	Memory
475595		stefantaga	Treasure Hunt (CEOI11_tre)	C++14	50 / 100	582 ms	67068 KiB

Main

#include <bits/stdc++.h>
#include "treinc.h"
using namespace std;
int acum,niv[400005];
void init()
{
    acum=2;
    niv[1]=1;
}
int tata[20][400005];
int lg=19,inainte,j;
void path (int a,int s)
{
    inainte=a;
    int i;
    for (i=acum; i<=acum+s-1; i++)
    {
        niv[i]=niv[inainte]+1;
        tata[0][i]=inainte;
        inainte=i;
    }
    for (j=1; j<=19; j++)
    {
        for (i=acum; i<=acum+s-1; i++)

        {
            tata[j][i]=tata[j-1][tata[j-1][i]];
        }
    }
    acum=acum+s;
}
int tatic(int x,int dist)
{
    int acum,i;
    acum=x;
    for (i=0; i<=19; i++)
    {
        if ((dist&(1<<i)))
        {
            acum=tata[i][acum];
        }
    }
    return acum;
}
int lca(int x,int y)
{
    if (niv[x]<niv[y])
    {
        return lca(y,x);
    }
    int dif=niv[x]-niv[y];
    x=tatic(x,dif);
    if (x!=y)
    {
        for (int i=19; i>=0; i--)
        {
            if (tata[i][x]!=tata[i][y])
            {
                x=tata[i][x];
                y=tata[i][y];
            }
        }
        x=tata[0][x];
    }
    return x;
}
int dig(int x,int y)
{
    int salut=lca(x,y);
    int stanga=niv[x]-niv[salut],dreapta=niv[y]-niv[salut];
    int dist=(stanga+dreapta)/2;
    if (dist<=stanga)
    {
        return tatic(x,dist);
    }
    else
    {
        dreapta=dreapta-(dist-stanga);
        return tatic(y,dreapta);
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10