Cod sursă (job #786077)

#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)
{
    if(x==0)
        return 0;
    if(distInChunk[x]!=0)
        return distInChunk[x];
    if(getChunkID(x)!=getChunkID(nextID[x]))
        return distInChunk[x];
    return getDistInChunk(nextID[x])+1;
}

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

int ChunkLastUpdate[316];

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

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

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;
    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);

    for(i=1; i<=n; i++)
    {
        fscanf(fin, "%d", &nextID[i]);
        UpdateStory(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);
            j=0;
            while(getChunkID(x)>=j)
            {
                if(ChunkLastUpdate[j]!=0)
                {
                    UpdateChunk(ChunkLastUpdate[j], n);
                    ChunkLastUpdate[j] = 0;
                }
                j++;
            }
            fprintf(fout, "%d\n", getDist(x));
        }
        else if(type==2)
        {
            fscanf(fin, "%d%d", &x, &y);
            nextID[x] = y;
            ChunkLastUpdate[getChunkID(x)] = x;
            //UpdateChunk(x, n);
        }
    }

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