Cod sursa(job #100)

Utilizator fluffyDan-Leonard Crestez fluffy Data 4 decembrie 2006 23:50:53
Problema Stramosi Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

FILE *fin, *fout;

#define MAX_LOG_N 18 
#define MAX_N (1 << MAX_LOG_N)
#define MAX_M (1 << 19)
#define MAX_LINE (8 * MAX_N)

int n, m;
int parent[MAX_N][MAX_LOG_N];
int query_node[MAX_M], query_depth[MAX_M];
char string[MAX_LINE];
int q[MAX_N];

int tok_string_to_int(const char* s)
{
    int nr, qe;
    nr = -1;
    qe = 0;
    for (; *s; ++s) {
        if (*s < '0' || *s > '9') {
            if (nr >= 0) {
                q[qe++] = nr;
                nr = -1;
            }
        } else {
            if (nr < 0) {
                nr = *s - '0';
            } else {
                nr = 10 * nr + *s - '0';
            }
        }
    }
    return qe;
}

void read(void)
{
    int i;
    memset(parent, 0, sizeof(parent));
    parent[0][0] = 0;
    
    fgets(string, sizeof(string), fin);
    tok_string_to_int(string);
    n = q[0];
    m = q[1];

    fgets(string, sizeof(string), fin);
    tok_string_to_int(string);
    for (i = 1; i <= n; ++i) {
        parent[i][0] = q[i - 1];
    }

    for (i = 0; i < m; ++i) {
        fgets(string, sizeof(string), fin);
        tok_string_to_int(string);
        query_node[i] = q[0];
        query_depth[i] = q[1];
    }
}

int get(int a, int b)
{
    if (parent[a][b] >= 0) {
        return parent[a][b];
    } else {
        return parent[a][b] = get(get(a, b - 1), b - 1);
    }
}

void solve(void)
{
    int x, d, i, j;
    char *s, *ss;
    for (j = 1; j < MAX_LOG_N; ++j) {
        for (i = 1; i <= n; ++i) {
            parent[i][j] = parent[i][j - 1] ? parent[parent[i][j - 1]][j - 1] : 0;
        }
    }
/*    int qs, qe, nqe;
    qe = 0;
    for (i = 0; i <= n; ++i) {
        q[qe++] = i;
    }
    for (j = 1; j < MAX_LOG_N; ++j) {
        qs = nqe = 0;
        while (qs < qe) {
            i = q[qs++];
            parent[i][j] = parent[parent[i][j - 1]][j - 1];
            if (parent[i][j]) {
                q[nqe++] = i;
            }
        }
        qe = nqe;
    }*/
    s = string;
    for (j = 0; j < m; ++j) {
        x = query_node[j];
        d = query_depth[j];
        for (i = 0; d; ++i) {
            if (d & 1 << i) {
                d = d ^ (1 << i);
/*                x = get(x, i);*/
                x = parent[x][i];
            }
        }
        s += 1;
        if (x >= 10) ++s;
        if (x >= 100) ++s;
        if (x >= 1000) ++s;
        if (x >= 10000) ++s;
        if (x >= 100000) ++s;
        if (x >= 1000000) ++s;
        ss = s;
        *s = '\n'; --s;
        if (x) {
            while (x) {
                *s = '0' + x % 10; --s;
                x /= 10;
            }
        } else {
            *s = '0';
            --s;
        }
        s = ss + 1;
    }
    *s = 0;
    fputs(string, fout);
}

int main(void)
{
    fin = fopen("stramosi.in", "rt");
    fout = fopen("stramosi.out", "wt");
    read();
    solve();
    fclose(fin);
    fclose(fout);
    return 0;
}