CCO Preparation Test 1 P3 - K-th Rank Student

View as PDF

Submit solution

All submissions

Best submissions

Points: 17 (partial)

Time limit: 0.6s

Memory limit: 128M

Author:

bruce

Problem types

In Bruce's class, there are $N$ ~N~ students, numbered from $1$ ~1~ to $N$ ~N~. Bruce ranks his students in increasing order according to the number of questions they have solved on DMOJ. The student who solves the least number of questions is ranked 1st. Conveniently, no two students have solved the same number of questions, i.e. each student has a unique rank.

Bruce finds that some students are friends. Note that friendship is a bidirectional relationship. For example, if Alex is Tim's friend, then conversely, Tim is also Alex's friend. Students are grouped together through friendship. Now, Bruce wants to motivate his students to solve more questions on DMOJ. He will perform a sequence of operations, each of which is one of the following:

$B\ x\ y$ ~B\ x\ y~, build a friendship between student $x$ ~x~ and student $y$ ~y~;
$Q\ x\ k$ ~Q\ x\ k~, query the student number who has the $k$ ~k~-th lowest rank in the group that contains student $x$ ~x~ (note that the group of student $x$ ~x~ includes student $x$ ~x~ himself).

Input Specification

The first line of input will consist of two integers $N$ ~N~ and $M$ ~M~ ( $1 \le N \le 100\,000$ ~1 \le N \le 100\,000~, $0 \le M \le N$ ~0 \le M \le N~). $N$ ~N~ is the number of students and $M$ ~M~ is the number of initial friendships.

The second line of input is a permutation of $1$ ~1~ to $N$ ~N~, representing the rankings of all $N$ ~N~ students.

The next $M$ ~M~ lines of input will contain the initial friendships. It is guaranteed that the numbers of the students that are friends will be valid.

The next line of input is a single integer $q$ ~q~ ( $1 \le q \le 300\,000$ ~1 \le q \le 300\,000~), which is the total number of operations. Each of the next $q$ ~q~ lines will contain an operation, starting with $Q$ ~Q~ or $B$ ~B~ as described above.

Output Specification

For each query operation, i.e. $Q\ x\ k$ ~Q\ x\ k~, output an integer on a single line. The integer is the number of the student who ranks the $k$ ~k~-th lowest in the group of student $x$ ~x~. If there is no such student, output -1.

Sample Input

Sample Output

Comments

12

bossu commented on April 1, 2015, 11:49 a.m. ← edit 2 →

what is the best solution for this problem? i can only think of $N \log^2 N$ ~N \log^2 N~. is there a better one?

hahhahahh, i modified from reading with cin to reading with scanf and my execution time reduced 10 times

4

fifiman commented on March 10, 2015, 3:42 a.m.

Am i on the right track to the accepted solution? Thanks

10

FatalEagle commented on March 10, 2015, 3:46 a.m.

About halfway. Your merge function is $\mathcal{O}(N)$ ~\mathcal{O}(N)~.

4

fifiman commented on March 10, 2015, 4:32 a.m.

I've been having a tough time finding a sublinear merge