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

Partial Judge Header

Discuss

Description

Denny just learned the sorting method in school.

Sorting once is too easy for him, so the teacher asked a question that needs to be sorted twice to test him.

In this question, you will get a string V, and N strings of length 6, you need to sort the strings internally according to the order of the string V, and then sort the N strings in dictionary order. All strings contain only lower-case letters.

Input

The first line contains a integer N, the number of strings you need to sort

The second line contains a string V

The following line contains N strings S1 ~ SN

testcase:

(3/6) 1 <= N <= 100, V = abcdefghijklmnopqrstuvwxyz

(3/6) 1 <= N <= 100, V = the permutation of a~z

Output

The Output contains only one line, the sorted string after sorting.

note: remember to add a '\n' in the end of output

Sample Input  Download

Sample Output  Download

Discuss

Description

It doesn’t make any sense, but you are now a member of the literature club in a high school.

Currently, the director (社長) of the literature club, Monica, is worried about her homework from computer science class (she takes this course in high school due to 多元學習). As an outstanding student, Monica always finished her homework fast and perfectly. However, she is not quite good at computer science. Monica knows you are a 二類生, thus she asks you for help with the homework during today's club time. The problem is described below:

Given a preorder traversal sequence and a postorder traversal sequence of a binary tree. Then, given an inorder traversal sequence, answer whether these three sequences can construct a valid binary tree.

You won't want to disappoint Monica, so you better hurry.

Hint from Yuri's notebook: 
If you have no idea how to implement, please take it as your reference and thanks Yuri for her help.

By the way, Yuri wants to remind you that not every preorder sequence and inorder sequence could construct a binary tree. See sample input/output as reference.

#include <stdlib.h>
#include <stdio.h>
typedef struct _node {
    int value;
    struct _node *left;
    struct _node *right;
} Node;

// create a new node
Node *create_node(int value);
// verify whether the postorder is match with the input
int verify(Node *root, int *postorder);
// free the memory
void destroy(Node *root);

/*
    Parameter description:
    int *inorder : the inorder traversal sequence of the binary tree.
    int *preorder : the preorder traversal sequence of the binary tree.
    int inorder_start : the starting index of the inorder traversal of the subtree.
    int inroder_end : the ending index of the inorder traversal of the subtree.

    As for the preorder traversal index, you can try declaring a global variable.
*/
// build the tree using recursive
Node *build(int *inorder, int *preorder, int inorder_start, int inorder_end);

Input

The first line of input contains an integer N, indicating the number of nodes on the tree.
The second line contains N distinct numbers, which is the preorder traversal sequence of the binary tree.
The third line contains N distinct numbers, which is the postorder traversal sequence of the binary tree.
Then, the fourth line contains an integer Q, indicating the number of queries.
The following Q lines each contain N distinct numbers, which is the inorder traversal sequence of the binary tree.

Constraints:

1 ≤ N ≤ 2 x 10⁵
1 ≤ Q ≤ 20
For all x being the number on the binary tree, 0 ≤ x ≤ N-1.

Output

Output contains Q lines. For each query, print ‘Yes’ if the three sequences could construct a valid binary tree, otherwise print ‘No’.

Sample Input  Download

Sample Output  Download

Discuss

Description

Story

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

Red Cape Flying Cat and penguins are playing a game on a tree. The penguins each stand on a different node. To prevent them from falling off the tree, Red Cape Flying Cat wants to find the lowest common ancestor of the penguins, so that he can protect both of them at once and make sure neither of them stays airborne for too long.

Problem Statement

Given a rooted binary tree with n nodes, where node 1 is the root. Each node has at most 2 children. The depth of the root is defined as 1, and the depth of any other node is the depth of its parent plus one.

Output the depth of every node, and answer q queries. Each query gives two nodes u and v; output their Lowest Common Ancestor (LCA) — the node that is an ancestor of both u and v and has the greatest depth.

Note that a node is considered an ancestor of itself.

You may use the following template to solve this problem:

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

typedef struct Node {
    int idx;
    struct Node *parent, *leftChild, *rightChild;
    int dep, vis;
} Node;

Node* tree[10005];

int main() {
    // init
    for (int i = 0; i < 10005; i++) {
        tree[i] = (Node*)malloc(sizeof(Node));
        tree[i]->idx = i;
        tree[i]->parent = NULL;
        tree[i]->leftChild = NULL;
        tree[i]->rightChild = NULL;
        tree[i]->dep = 0;
        tree[i]->vis = 0;
    }
}

Explanation

The tree has 4 nodes. From the parent array 1 1 2, we know:

• Node 2's parent is node 1
• Node 3's parent is node 1
• Node 4's parent is node 2

So the tree looks like this:

    1        (depth 1)
   / \
  2   3      (depth 2)
  |
  4          (depth 3)

The depth output is 1 2 2 3.

Query 1: LCA(4, 4) = 4
The LCA of a node with itself is the node itself.

Query 2: LCA(2, 4) = 2
The ancestors of node 4 are: 4, 2, 1. The ancestors of node 2 are: 2, 1. The deepest common ancestor is node 2.

Query 3: LCA(4, 3) = 1
The ancestors of node 4 are: 4, 2, 1. The ancestors of node 3 are: 3, 1. The deepest common ancestor is node 1.

Input

n
p2 p3 ... pn
q
u1 v1
u2 v2
...
uq vq

• n: number of nodes in the tree
• pi: parent of node i, for i = 2, 3, ..., n
• q: number of queries
• ui, vi: the two nodes of the i-th query
• If n = 1, the second line is empty.

Constraints

• 1 <= n <= 10^4
• 1 <= pi <= n, pi != i
• The input is guaranteed to form a tree rooted at node 1
• The tree is guaranteed to be a binary tree (each node has at most 2 children)
• 1 <= q <= 10^4
• 1 <= ui, vi <= n

Output

d1 d2 d3 ... dn
lca1
lca2
...
lcaq

• di: depth of node i
• lcai: the LCA node of the i-th query

Note that there must be no trailing space after the last depth value.

Sample Input  Download

Sample Output  Download

Discuss