URAL 1329. Galactic History

Author: nex3z 2015-08-22

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1329

1329. Galactic History

Time limit: 1.0 second
Memory limit: 64 MB

2. 思路

银河系历史被划分为由里程碑构成的树状结构，给出若干里程碑及其父子关系，并给出若干查询条目，求每个查询条目中两个里程碑间的关系（一个是另一个的根，或者没有关系）。

由输入数据给出的各里程碑关系，构建一个树，没有难度。此题的陷阱在于，查询条目最多有40000条，如果一条一条查，会超时；需要在对树的一次遍历中，把所有条目查询完。

在下面的代码中，使用aList[i] 和bList[i] 分别存储第i个查询中包含的两个里程碑A和B，用statusList[i] 表示第i个查询条目的查询状态，初始化为STATUS_NOT_FOUND 。同时，以邻接表的形式保存每个查询，每个查询对应一个结构体Query ，Query 有两个字段，queryId 和next ：queryId 为查询条目的id，statusList[queryId] 、aList[queryId] 和bList[queryId] 分别对应了queryId 查询条目的查询状态、A和B；next 指向下个Query ，使得对于每个里程碑m，query[m] 成为一个链表，存储了所有包含有m的查询。

对树进行一次先序遍历，对于每个节点n，通过query[n] 可以得到所有包含有n的查询，对于每个包含有n查询，根据其queryId ，由statusList[queryId] 得到该查询的状态，进行相应处理：

• 如果statusList[queryId] 为STATUS_NOT_FOUND ，则若当前节点n == aList[queryId] ，则令statusList[queryId] = STATUS_FOUND_A ；若当前节点n == bList[queryId] ，则令statusList[queryId] = STATUS_FOUND_B ；
• 如果statusList[queryId]为STATUS_FOUND_A ，则若当前节点n == bList[queryId] ，查询完成，令statusList[queryId] = STATUS_A_IS_ROOT_OF_B ；
• 如果statusList[queryId]为STATUS_FOUND_B ，则若当前节点n == aList[queryId] ，查询完成，令statusList[queryId] = STATUS_B_IS_ROOT_OF_A ；

每遍历完一棵子树，检查一遍statusList[] ：如果其中有STATUS_FOUND_A ，说明在这个子树中，只找到了这个查询中的里程碑A，对于查询中的另一个里程碑B，可能在别的子树或根本不存在，查询失败，将其查询状态置为STATUS_NONE ；同理对于STATUS_FOUND_B ，也表明查询失败，置为STATUS_NONE 。

3. 代码

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 40010
#define MAX_L 40010

#define STATUS_NONE 0
#define STATUS_A_IS_ROOT_OF_B 1
#define STATUS_B_IS_ROOT_OF_A 2
#define STATUS_NOT_FOUND 3
#define STATUS_FOUND_A 4
#define STATUS_FOUND_B 5

struct MilestoneRecord;
typedef struct MilestoneRecord Milestone;
typedef Milestone *PtrToMilestone;
struct QueryRecord;
typedef struct QueryRecord Query;
typedef Query *PtrToQuery;

void solveE2e();
int inputMilestones(Milestone milestone[], int n);
void printMilestone(Milestone milestone[], int root);
void inputQueries(int aList[], int bList[], int statusList[], Query query[], int l);
void performQuery(int root);

struct MilestoneRecord{
    int childId;
    PtrToMilestone next;
};

struct QueryRecord{
    int queryId;
    PtrToQuery next;
};

int main() {
    solveE2e();
    return 0;
}

Milestone milestone[MAX_N];
Query query[MAX_L];
int aList[MAX_L], bList[MAX_L], statusList[MAX_L];
void solveE2e() {
    int n, root, l, i;

    scanf("%d", &n);
    root = inputMilestones(milestone, n);

    scanf("%d", &l);
    inputQueries(aList, bList, statusList, query, l);
    //printMilestone(milestone, root);

    performQuery(root);

    for (i = 0; i < l; ++i) {
        printf("%d ", statusList[i]);
    }
    printf("\n");
}

int inputMilestones(Milestone milestone[], int n) {
    int root, i, childId, parentId;
    PtrToMilestone tmp;

    for (i = 0; i < n; ++i) {
        scanf("%d %d", &childId, &parentId);
        if (parentId == -1) {
            root = childId;
        } else {
            tmp = malloc(sizeof(Milestone));
            tmp->childId = childId;
            tmp->next = milestone[parentId].next;
            milestone[parentId].next = tmp;
        }
    }

    return root;
}

void inputQueries(int aList[], int bList[], int statusList[], Query query[], int l) {
    int i, a, b;
    PtrToQuery tmp;
    
    for (i = 0; i < l; ++i) {
        scanf("%d %d", &a, &b);
        aList[i] = a;
        bList[i] = b;
        statusList[i] = STATUS_NOT_FOUND;

        tmp = malloc(sizeof(Query));
        tmp->queryId = i;
        tmp->next = query[a].next;
        query[a].next = tmp;

        tmp = malloc(sizeof(Query));
        tmp->queryId = i;
        tmp->next = query[b].next;
        query[b].next = tmp;
    }
}

void performQuery(int root) {
    int queryId, a, b;
    PtrToQuery relatedQuery;
    PtrToMilestone child;

    relatedQuery = query[root].next;
    while (relatedQuery != NULL) {
        queryId = relatedQuery->queryId;
        a = aList[queryId];
        b = bList[queryId];
        if (statusList[queryId] == STATUS_NOT_FOUND) {
            if (a == root)
                statusList[queryId] = STATUS_FOUND_A;
            else if (b == root)
                statusList[queryId] = STATUS_FOUND_B;
        }
        else if (statusList[queryId] == STATUS_FOUND_A) {
            if (b == root)
                statusList[queryId] = STATUS_A_IS_ROOT_OF_B;
        }
        else if (statusList[queryId] == STATUS_FOUND_B) {
            if (a == root)
                statusList[queryId] = STATUS_B_IS_ROOT_OF_A;
        }
        relatedQuery = relatedQuery->next;
    }

    child = milestone[root].next;
    while (child != NULL) {
        performQuery(child->childId);
        child = child->next;
    }

    relatedQuery = query[root].next;
    while (relatedQuery != NULL) {
        queryId = relatedQuery->queryId;
        if (statusList[queryId] == STATUS_FOUND_A || statusList[queryId] == STATUS_FOUND_B)
            statusList[queryId] = STATUS_NONE;
        relatedQuery = relatedQuery->next;
    }
}

void printMilestone(Milestone milestone[], int root) {
    int queryId;
    PtrToMilestone child;
    PtrToQuery relatedQuery;

    printf("Milestone %d: ", root);
    child = milestone[root].next;
    while (child != NULL) {
        printf("%d ", child->childId);
        child = child->next;
    }
    printf("\n");

    printf("Query: ");
    relatedQuery = query[root].next;
    while (relatedQuery != NULL) {
        queryId = relatedQuery->queryId;
        printf("(%d: %d %d %d) ", queryId, aList[queryId], bList[queryId], statusList[queryId]);
        relatedQuery = relatedQuery->next;
    }
    printf("\n\n");

    child = milestone[root].next;
    while (child != NULL) {
        printMilestone(milestone, child->childId);
        child = child->next;
    }
}