Cod sursă (job #785992)

#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 dist[100001];

int getDist(int x)
{
    if(x==0)
        return 0;
    if(dist[x]!=0)
        return dist[x];
    return getDist(nextID[x])+1;
}

int main()
{
    FILE *fin, *fout;
    int n, q, i, type, x, y, lastupdID=0;
    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]);

    for(i=0; i<q; i++)
    {
        fscanf(fin, "%d", &type);
        if(type==1)
        {
            fscanf(fin, "%d", &x);
            while(lastupdID<x)
            {
                lastupdID++;
                dist[lastupdID] = 0;
                dist[lastupdID] = getDist(lastupdID);
            }
            fprintf(fout, "%d\n", getDist(x));
        }
        else if(type==2)
        {
            fscanf(fin, "%d%d", &x, &y);
            nextID[x] = y;
            if(lastupdID>=x)
                lastupdID = x-1;
        }
    }

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