With all of Ook's pet fish to teach, Haymouth barely has any time left to himself. No more dancing for bananas or sabotaging servers. In fact, being a rather feeble-minded cow, Haymouth hasn't been able to teach fish anything substantial at all, much to Ook's dismay. The only thing he has accomplished so far is to prevent the magical rainbow fish from talking in class, but even that wasn't very effective. Magical rainbow fish, being magical rainbow fish, can still rapidly change colour and make magical rainbows which are even more distracting.
Haymouth has long since given up on ignoring the magical rainbows and has instead taken to observing them. In fact, he finds them quite interesting! The rainbow fish turn out to make magical rainbows in a very specific way, possibly to distract him and prevent class from progressing, but Haymouth hasn't picked up on that yet.
The N fish are one big family. In other words, each fish has children, which might possibly have their own children, and so on. There is only one fish without a parent.
To keep the fish on their fins, Haymouth asks the class two questions at a time. Each question is directed to exactly one fish. Fish do not like to answer questions, so whenever Haymouth asks the two questions, the lowest common ancestor of the two fish the questions were directed to will make a magical rainbow. This distracts Haymouth, who promptly forgets that the questions need to be answered at all.
Haymouth is determined to get to the bottom of all the magical rainbow-making. He decided that he needs to know each fish's parent. This will allow him to predict which fish will make the rainbow and prevent him from getting distracted. However, the fish are one step ahead of him and will change their rainbow-making strategy after R rainbows. Help Haymouth to figure out every fish's parent before the fish change their strategy.
Implementation
You are to implement the function void findParents(int N, int R, int K);.
N is the number of fish in your class.R is the maximum number of rainbows you can observe before the fish will change their strategy.K is the subtask number, described below.
In your implementation, you are allowed to call the function int makeRainbow(int a, int b);.
- The fish are numbered from 1 to N.
a and b should be integers that satisfy 1 ≤ a, b ≤ N.- The function will return the label of the fish that made the magical rainbow after Haymouth asked fish a and fish b questions.
- You should call this function a maximum of R times.
When findParents(N, R, K) is called, it should call the function void foundParent(int a, int b); a maximum of N times.
a and b should satisfy 1 ≤ a ≤ N, 0 ≤ b ≤ N.- This means that you have deduced that the parent of a is b. In the case that a has no parent, b should be 0.
- You should not call this function more than once for the same a.
Constraints
In all testcases, the following constraints hold:
- 1 ≤ N ≤ 100 000.
- No fish has more than 16 children.
Scoring
Each subtask has a number of test cases. The score you receive for each subtask will be a percentage of the maximum score for that subtask. The percentage is the average score over all test cases within the subtask.
For each test case, your score will be 0 if you violate any of the constraints for calling the functions described above. Otherwise, your score depends on the accuracy of your deductions. Let C be the number of fish for which you have deduced the parent correctly and W be the number of fish for which the parent you inferred is incorrect. Your score for the test case will be 100 * max(0, (C / N)1/2 - W2 / N).
Subtasks
Subtask 1 (29 points):
- K = 1.
- 1 ≤ N ≤ 1 000.
- R = N * (N - 1) / 2.
Subtask 2 (17 points):
- K = 2.
- R = 17 * N.
- No fish has more than 1 child.
Subtask 3 (54 points):
Sample Input 1
4 6 1
4
3
0
3
Sample Input 2
10 170 2
0
1
2
3
4
5
6
7
8
9
Sample Input 3
20 1400 3
13
16
7
16
7
2
13
0
4
3
7
19
8
16
1
3
2
2
5
4
