Write a program to record club information and answer queries.
Task Description
There are at most N clubs for M students to create or join. Each student can create or join as many clubs as he wishes. All students and clubs have their own names. We record club information according to a sequence of instructions. Each instruction consists of a number (0 or 1) and two strings. The first string is the student name, and the second string is the club name.
If the instruction is 0 A B, indicating that student A creates club B.
If the instruction is 1 A B, indicating that student A joins club B.
For example, if the instruction is 0 Sara Tennis. It means that Sara creates a club named "Tennis", and she is not only the member but also the leader of Tennis club. If the instruction is 1 John Dance, it means that John joins the club "Dance", and becomes a member of Dance club.
After students join the clubs, you need to answer a series of queries code. There are two kinds of queries. Each query starts with a number either 0 or 1.
The first kind of query consists of a 0 and a string for a club name. For example, 0 A is a query asking for the name of leader the club A.
The answer should be a string for the name of the leader if club A exists.
The answer should be "None" if club A does not exist.
The second kind of query consists of a 1 and two strings. The first string is a student name, and the second string is a club name. For example, 1 A B is a query asking if the student A is a member or the leader of club B.
If club B exists then return the following. If A is a member or the leader of club B the answer is 1; otherwise, the answer is 0.
If club B does not exist the answer should be -1.
We use the previous 0 Sara Tennis and 1 John Dance as examples. Now if the query is 0 Tennis, the answer is "Sara" since Sara is the leader of Tennis club. If the query is 1 Sara Dance, the answer is 0 since Sara is not a member of Dance club. If the query code is 1 Angela Dance, the answer is 0 since we cannot find "Angela" in the Dance club.
Write a program to record the clubs information and answer queries. It is guaranteed that a club will be created before other students can join it. And no two clubs have the same name, and a club will be created only once.
Subtask
20 points: Each club has only the leader and no other members.
20 points: There is only one club.
60 points: Nothing is guaranteed. Note that you will get TLE if you put information in an array and search through it to answer queries.
Input Format
The input contains only one test case. The first line contains an integer K, where K is the number of instructions. For the following K lines, each line contains one instruction. The line after K+1 lines contains an integer Q, where Q is the number of inquiries. For the following Q lines, each line contains one query code.
K <= 100000, Q <= 100000.
N <= 10000, M <= 10000.
Name length is no longer than 40.
Output Format
Print the results of a series of inquiries. Each line contains a result.
Sample Input 1
5
0 Sara Tennis
0 John Dance
0 Una Singing
0 Rex Badminton
0 C TESTEST
6
0 Tennis
1 John Tennis
1 Una Singing
1 Rex TESTEST
0 CCC
1 JJJ TESTEST
Sample Output 1
Sara
0
1
0
None
0
Sample Input 2
5
0 Sara Tennis
1 John Tennis
1 Una Tennis
1 Rex Tennis
1 C Tennis
6
0 Singing
1 John Tennis
1 Una Singing
0 Tennis
1 Rex Tennis
1 JJJ Tennis
Sample Output 2
None
1
-1
Sara
1
0
Sample Input 3
9
0 Sara Tennis
1 John Tennis
0 John Dance
1 Una Tennis
0 Una Singing
0 Rex Badminton
0 C TESTEST
1 Rex Tennis
1 C Tennis
8
0 Tennis
1 John Tennis
1 Una Singing
1 Rex TESTEST
0 Singing
1 Kay TESTEST
1 C TESTEST
0 Rex
Sample Output 3
Sara
1
1
0
Una
0
1
None
Note
To process a large amount of queries, you need to build a binary search tree for all clubs. Each tree node will have the name of the club and the name of its leader. By using a binary search tree, one can easily check if a given club exists. In addition, from each club node you also need to build a binary search tree for all members of this club, so that you can easily check if a student is in that club. That is, each node of this tree contains a student name. Consequently, the tree for clubs should be arranged by the club names, and the tree for club members should be arranged by the student names.
Write a program to record club information and answer queries.
Task Description
There are at most N clubs for M students to create or join. Each student can create or join as many clubs as he wishes. All students and clubs have their own names. We record club information according to a sequence of instructions. Each instruction consists of a number (0 or 1) and two strings. The first string is the student name, and the second string is the club name.
0 A B, indicating that student A creates club B.1 A B, indicating that student A joins club B.For example, if the instruction is
0 Sara Tennis. It means that Sara creates a club named "Tennis", and she is not only the member but also the leader of Tennis club. If the instruction is1 John Dance, it means that John joins the club "Dance", and becomes a member of Dance club.After students join the clubs, you need to answer a series of queries code. There are two kinds of queries. Each query starts with a number either 0 or 1.
0 Ais a query asking for the name of leader the club A.1 A Bis a query asking if the student A is a member or the leader of club B.We use the previous
0 Sara Tennisand1 John Danceas examples. Now if the query is0 Tennis, the answer is "Sara" since Sara is the leader of Tennis club. If the query is1 Sara Dance, the answer is 0 since Sara is not a member of Dance club. If the query code is1 Angela Dance, the answer is 0 since we cannot find "Angela" in the Dance club.Write a program to record the clubs information and answer queries. It is guaranteed that a club will be created before other students can join it. And no two clubs have the same name, and a club will be created only once.
Subtask
Input Format
The input contains only one test case. The first line contains an integer K, where K is the number of instructions. For the following K lines, each line contains one instruction. The line after K+1 lines contains an integer Q, where Q is the number of inquiries. For the following Q lines, each line contains one query code.
Output Format
Print the results of a series of inquiries. Each line contains a result.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Sample Input 3
Sample Output 3
Note
To process a large amount of queries, you need to build a binary search tree for all clubs. Each tree node will have the name of the club and the name of its leader. By using a binary search tree, one can easily check if a given club exists. In addition, from each club node you also need to build a binary search tree for all members of this club, so that you can easily check if a student is in that club. That is, each node of this tree contains a student name. Consequently, the tree for clubs should be arranged by the club names, and the tree for club members should be arranged by the student names.