Description

Given several operations, push x, pop, print, reverse, create a linked list dynamicly.

• push x: Add one Node (with data = x) at the front of linked list.
• pop: Delete the Node at the front of linked list.
• reverse: reverse the current linked list
• print: output the linked list in given format.

You have to implement 3 functions:

1. void Push(Node** ptr_head,int x)
2. void Pop(Node** ptr_head)
3. void Reverse_List(Node** ptr_head)

Note: Modify the Node* head by Node** ptr_head

Input

There’re operations on several lines.
All operations are one of push x, pop, print, reverse.
It’s guaranteed that:

• Number of operations is less than 5,000,000
• Integer x is in [−1000,1000]
• The maximum length of linked list is less than 10,000.

Output

Output the linked list for every print.

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

12568.c

Partial Judge Header

12568.h

Tags

Discuss

Description

Important Note

Before submitting your code:

1. You must submit implementations for all functions (the function body may be empty).
2. You must submit all header files you use.

Otherwise, you may receive a Compile Errorr.

Story

(The following story is irrelevant to the problem description.)

Red Cape Flying Cat spotted the penguins playing in the trees and happily joined in. As they leaped from branch to branch together, Red Cape Flying Cat grew curious: from any position in the tree, how high up can you reach by jumping in powers of two? Being a CS student, he only cares about which node you land on after jumping exactly 2^j steps upward. Since he is still busy playing with the penguins, please write a program to help him figure it out.

Problem Statement

This is a partial judge problem.

In a single test case, the total number of function calls will not exceed 5*10^3.

You are given a rooted binary tree with n nodes (1 <= n <= 10^4), numbered 1 to n. Node 1 is always the root.

Each node is defined as the following structure:

typedef struct Node {
    int idx;
    struct Node *parent, *leftChild, *rightChild;
    int vis;                // for auxiliary use, initialized to 0
    int dep;                // pre-filled by main.c

    int subtreeSize;        // TODO: filled by find_subtree_size
    struct Node* jump[14];  // TODO: filled by build_jump
} Node;

The main.c reads the input and constructs the tree by setting parent, leftChild, and rightChild for each node. Children are always assigned to the left child first — a node will never have a right child without also having a left child.

The dep field of every node is pre-filled by main.c before any function is called.

You need to implement the following 4 functions:

The following tree with n = 5 is used as a reference for all examples below:

1. Find LCA

 

Goal

Your goal is to implement a function that, given two nodes u and v, returns a pointer to their Lowest Common Ancestor (LCA):

Node* find_lca(Node* u, Node* v);

The LCA of nodes u and v is the deepest node that is an ancestor of both u and v. Node a is an ancestor of node b if a lies on the path from b to the root (inclusive of a and b themselves). If u == v, return u.

 

Constraint

• 1 <= u->idx, v->idx <= n
• Before this function is called, the vis field of every node is guaranteed to be 0.

 

Example

Using the same tree (n = 5):

code:

printf("lca: %d\n", find_lca(tree[4], tree[5])->idx);
printf("lca: %d\n", find_lca(tree[4], tree[3])->idx);
printf("lca: %d\n", find_lca(tree[3], tree[3])->idx);

output:

lca: 2
lca: 1
lca: 3

explanation:

---

 

2. Find Subtree Size

 

Goal

Your goal is to implement a function that computes the subtree size of every node in the tree:

void find_subtree_size(Node* root);

The subtree size of a node is defined as: the number of nodes in the subtree rooted at that node, including the node itself. Store the subtree size of each node in its subtreeSize field.

This function is called at most once per test case.

 

Constraint

• When called, root is always tree[1]

 

Example

Using the same tree (n = 5):

code:

find_subtree_size(tree[1]);
printf("subtree size: [%d, %d, %d, %d, %d]\n",
       tree[1]->subtreeSize, tree[2]->subtreeSize, tree[3]->subtreeSize,
       tree[4]->subtreeSize, tree[5]->subtreeSize);

output:

subtree size: [5, 3, 1, 1, 1]

explanation:

---

 

3. Find Distance

 

Goal

Your goal is to implement a function that, given two nodes u and v, returns the distance between them:

int find_distance(Node* u, Node* v);

The distance between u and v is the number of edges on the unique path connecting them. If u == v, return 0.

 

Constraint

• 1 <= u->idx, v->idx <= n
• The dep field of every node is guaranteed to be pre-filled before this function is called.
• Before this function is called, the vis field of every node is guaranteed to be 0.

 

Example

Using the same tree (n = 5):

code:

printf("distance: %d\n", find_distance(tree[4], tree[5]));
printf("distance: %d\n", find_distance(tree[4], tree[3]));
printf("distance: %d\n", find_distance(tree[3], tree[3]));

output:

distance: 2
distance: 3
distance: 0

explanation:

---

 

4. Build Jump Table

 

Goal

Your goal is to implement a function that builds the binary lifting table:

void build_jump(Node* tree[], int n);

The binary lifting table of a node is defined as: node->jump[j] is the node reached by going up 2^j steps from that node, for 0 <= j < 14. Store the result in node->jump[j] for every node tree[1] through tree[n]. If going up 2^j steps would pass the root, the result is the root itself. In particular, tree[1]->jump[j] = tree[1] for all j >= 0.

This function is called at most once per test case.

 

Constraint

• 1 <= n <= 10^4

 

Example

Using the same tree (n = 5):

code:

build_jump(tree, 5);
printf("jump table:\n");
for (int i = 1; i <= 5; i++) {
    for (int j = 0; j < 14; j++)
        printf("%d%c", tree[i]->jump[j]->idx, j < 13 ? ' ' : '\n');
}

output:

jump table:
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 1

explanation:

Subtask

Input

The first line contains a single integer n (1 <= n <= 10^4), the number of nodes in the binary tree.

The second line contains n - 1 space-separated integers: par[2] par[3] ... par[n], where par[i] is the parent of node i. (If n = 1, this line is omitted.)

Guarantee: Children are always assigned to the left child first — a node will never have a right child without also having a left child.

The third line contains a single integer q (1 <= q <= 5*10^3), the total number of function calls.

Each of the following q operations is formatted as follows:

find_lca

1 <u> <v>

find_subtree_size

2

find_distance

3 <u> <v>

build_jump

4

Guarantee: Operations 2 and 4 each appear at most once in the input.

Output

The output for each function call is as follows:

find_lca

lca: <result>

find_subtree_size

subtree size: [<tree[1]->subtreeSize>, <tree[2]->subtreeSize>, ..., <tree[n]->subtreeSize>]

find_distance

distance: <result>

build_jump

jump table:
<tree[1]->jump[0]->idx> <tree[1]->jump[1]->idx> ... <tree[1]->jump[13]->idx>
<tree[2]->jump[0]->idx> <tree[2]->jump[1]->idx> ... <tree[2]->jump[13]->idx>
...
<tree[n]->jump[0]->idx> <tree[n]->jump[1]->idx> ... <tree[n]->jump[13]->idx>

Sample Input  Download

Sample Output  Download

Partial Judge Code

14930.c

Partial Judge Header

14930.h

Tags

Discuss