Cod sursă (job #786441)

#include <bits/stdc++.h>

using namespace std;

int chunkSize;
int getChunkSize(int n)
{
    float rad = sqrt(n);
    int dec = floor(rad);
    if(rad-dec>0)
        return dec+1;
    else
        return dec;
}

int getChunkID(int i)
{
    return i/chunkSize;
}

int nextID[100001];
int distInChunk[100001];
int outOfChunkID[100001];

int getDistInChunk(int x, int lowerChunkBound)
{
    if(x==0)
        return 0;
    if(distInChunk[x]!=0)
        return distInChunk[x];
    if(nextID[x]<lowerChunkBound)
        return distInChunk[x];
    return getDistInChunk(nextID[x], lowerChunkBound)+1;
}

int getOutOfChunkID(int x, int lowerChunkBound)
{
    if(lowerChunkBound==0)
        return 0;
    if(outOfChunkID[x]!=0)
        return outOfChunkID[x];
    if(nextID[x]<lowerChunkBound)
        return nextID[x];
    return getOutOfChunkID(nextID[x], lowerChunkBound);
}

void UpdateStory(int x, int lowerChunkBound)
{
    distInChunk[x] = 0;
    distInChunk[x] = getDistInChunk(x, lowerChunkBound);
    outOfChunkID[x] = 0;
    outOfChunkID[x] = getOutOfChunkID(x, lowerChunkBound);
}

void UpdateChunk(int x, int n, int lowerChunkBound, int upperChunkBound)
{
    UpdateStory(x, lowerChunkBound);
    if(x+1<upperChunkBound && x+1<=n)
        UpdateChunk(x+1, n, lowerChunkBound, upperChunkBound);
}

int getDist(int x)
{
    if(getChunkID(x)==0)
        return distInChunk[x];
    return distInChunk[x]+1+getDist(outOfChunkID[x]);
}

int main()
{
    FILE *fin, *fout;
    int n, q, i, j, type, x, y, lowBound;
    fin = fopen("burlane.in", "r");
    fout = fopen("burlane.out", "w");

    fscanf(fin, "%d%d", &n, &q);
    chunkSize = getChunkSize(n+1);
    //fprintf(fout, "%d\n", chunkSize);
    i=1;
    j = 0;
    while(j<=n+1)
    {
        j += chunkSize;
        while(i<=n && i<j)
        {
            fscanf(fin, "%d", &nextID[i]);
            UpdateStory(i, j-chunkSize);
            i++;
        }
    }

    /*for(i=0; i<=n; i++)
    {
        fprintf(fout, "%d %d %d\n", distInChunk[i], outOfChunkID[i], getDist(i));
    }*/

    for(i=0; i<q; i++)
    {
        fscanf(fin, "%d", &type);
        if(type==1)
        {
            fscanf(fin, "%d", &x);
            fprintf(fout, "%d\n", getDist(x));
        }
        else if(type==2)
        {
            fscanf(fin, "%d%d", &x, &y);
            nextID[x] = y;
            UpdateChunk(x, n, getChunkID(x)*chunkSize, (getChunkID(x)+1)*chunkSize);
        }
    }

    fclose(fin);
    fclose(fout);
    return 0;
}