Cod sursa(job #1964946)

Utilizator preda.andreiPreda Andrei preda.andrei Data 13 aprilie 2017 20:32:42
Problema Lowest Common Ancestor Scor 90
Compilator c Status done
Runda Arhiva educationala Marime 2.51 kb
#include <stdio.h>
#include <stdlib.h>
 
#define LOG 20
 
typedef struct ListNode
{
    int value;
    struct ListNode *next;
} ListNode;
 
typedef struct List
{
    ListNode *left, *right;
} List;
 
ListNode *CreateListNode(int value)
{
    ListNode *new_node = (ListNode*)malloc(sizeof(ListNode));
    *new_node = (ListNode){value, NULL};
    return new_node;
}
 
void AddToList(List *list, int value)
{
    ListNode *new_node = CreateListNode(value);
    if (list->left == NULL) {
        list->left = list->right = new_node;
    } else {
        list->right->next = new_node;
        list->right = new_node;
    }
}
 
typedef struct TreeNode
{
    int ancestors[LOG];
    int nanc;
 
    int exit;
    List sons;
} TreeNode;
 
TreeNode* CreateTree(int size)
{
    TreeNode *tree = (TreeNode*)malloc(size * sizeof(TreeNode));
    int i;
 
    for (i = 0; i < size; ++i) {
        tree[i].nanc = tree[i].exit = 0;
        tree[i].sons = (List){NULL, NULL};
    }
    return tree;
}
 
void Dfs(TreeNode *t, int node, int st[], int nst)
{
    static int time = 0;
    st[nst] = node;
 
    if (nst > 0) {
        int fa = st[nst - 1];
        int ord = 1;
 
        t[node].ancestors[0] = fa;
        while ((1 << ord) < nst) {
            t[node].ancestors[ord] = t[fa].ancestors[ord - 1];
            fa = t[fa].ancestors[ord - 1];
            ++ord;
        }
        t[node].nanc = ord;
    }
 
    ListNode *it = t[node].sons.left;
    while (it != NULL) {
        Dfs(t, it->value, st, nst + 1);
        it = it->next;
    }
    t[node].exit = ++time;
}
 
void Swap(int *a, int *b)
{
    int aux = *a;
    *a = *b;
    *b = aux;
}
 
int Lca(TreeNode *t, int x, int y)
{
    if (x == y) {
        return x;
    }
    if (t[x].exit > t[y].exit) {
        Swap(&x, &y);
    }
 
    int ind = 0;
    while (ind < t[x].nanc) {
    	int fa = t[x].ancestors[ind];
    	if (t[fa].exit > t[y].exit) {
    		break;
    	}
    	++ind;
    }
    if (ind > 0) {
	    --ind;
	}

    return Lca(t, y, t[x].ancestors[ind]);
}
 
int main()
{
    FILE *fin = fopen("lca.in", "r");
    FILE *fout = fopen("lca.out", "w");
 
    int n, q, i, fa, x, y;
    fscanf(fin, "%d%d",&n, &q);
 
    TreeNode *tree = CreateTree(n);
    for (i = 1; i < n; ++i) {
        fscanf(fin, "%d", &fa);
        AddToList(&tree[fa - 1].sons, i);
    }
 
    int *stack = (int*)malloc(n * sizeof(int));
    Dfs(tree, 0, stack, 0);
    free(stack);

    while (q--) {
        fscanf(fin, "%d%d", &x, &y);
        fprintf(fout, "%d\n", Lca(tree, x - 1, y - 1) + 1);
    }
    free(tree);
 
    return 0;
}