Problem Description
Peanut has been working at a company which is undergoing restructuring. There are N employees in the company, numbered 0 to N-1, and they are grouped into departments, where each department contains a subset of employees and each employee belongs in exactly one department. At first, all employees belong in their own individual department which only contains themselves and no one else.
Next up, the boss of the company arrives, and conducts a series of operations. These operations can be one of two types: merge_two or merge_all. In the merge_two operation, the boss points to two different employees, and merges the departments that the two employees belong to. If they belong in the same department, they will be confused for a moment, and then nothing will happen. In the merge_all operation, the boss selects two integers x and y where 0 ≤ x ≤ y < N, and the departments of all employees which are numbered between x and y inclusive are merged into one.
At any point, the boss might also want to know whether any two employees are in the same department. You have to answer those queries.
Implementation Details
This is a function call question. You are to implement these four functions:
void init(int N)
This function is called once only at the beginning of the interaction, and indicates to your program that there are N employees in the company. You should do any initialisation or precomputation necessary in this function.
void merge_two(int x, int y)
This function should merge the departments of employee x and y. If they are from the same department, nothing happens.
void merge_all(int x, int y)
This function should merge the departments of employees x to y. If they are all from the same department, nothing happens.
bool is_same_department(int x, int y)
This function should return true if employees x and y are from the same department, and false otherwise.
Under the Attachments tab, you are provided with a header file, sample grader, solution template, and a compile command. You are advised to test the solution locally before submission to the judge. A sample testcase simulating the sample interaction below is also included.
Limits
Subtask 1 (21%): Total number of calls ≤ 2000, 1 ≤ N ≤ 1000.
Subtask 2 (17%): Total number of calls ≤ 500000, 1 ≤ N ≤ 200000, there will be no calls to merge_all.
Subtask 3 (30%): Total number of calls ≤ 500000, 1 ≤ N ≤ 200000, for the calls to merge_two, x + 1 = y.
Subtask 4 (32%): Total number of calls ≤ 500000, 1 ≤ N ≤ 200000.
Subtask 5 (0%): Sample Testcases.
Sample Interaction
init(5) is called.
merge_two(0, 4) is called.
merge_all(1, 3) is called.
is_same_department(2, 4) is called. It should return
false.
merge_two(2, 0) is called.
is_same_department(3, 0) is called. It should return
true.