DMPG '17 S2 - Anime Conventions

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.6s
Java 8 1.0s
Python 2 2.5s
Python 3 2.5s
Memory limit: 64M
Java 8 128M
Python 2 128M
Python 3 128M

Problem types

In the distant land of yore, there lived a weeb king. As a weeb king, he valued anime above all else including roads. And so it came to be that, when it came time to go to the anime conventions, he realised his folly: there were no roads in his kingdom, whatsoever! Angered, he went to his chief adviser (you) and asked them to simulate Q actions:

  • A x y: Build a road between cities x and y.
  • Q x y: Check if cities x and y are connected by the roads.

Since you want to please the king (maybe he'll get you something nice from the next convention in return!), you'll have to answer his queries.

Input Specification

The first line will have two integers, N, and Q (2 \le N \le 10^5; 1 \le Q \le 10^5), the number of cities and queries, respectively.
The next Q lines each have a query. It is guaranteed that x \ne y; 1 \le x, y \le N.

For 30\% of points, 1 \le N, Q \le 1\,000.

Output Specification

For each query in the form Q x y, print Y if you can travel from city x to city y. Otherwise, print N.

Sample Input

5 6
A 1 2
A 2 3
Q 1 3
A 1 5
Q 5 2
Q 4 1

Sample Output



For the first query, the king can travel along the following path: 1 \to 2 \to 3

For the second query, the king can travel along the following path: 5 \to 1 \to 2

For the third query, there are no roads that connect to city 4.


  • 7
    jerry0101  commented on July 29, 2020, 5:14 p.m.

    can somebody give some pointers for my code

  • 1
    AndrewVII  commented on May 17, 2017, 8:40 p.m.

    Any optimization tips for my program?

    • 25
      wleung_bvg  commented on May 17, 2017, 10:32 p.m. edited

      Doing BFS for every query is not required. There is a data structure that can solve these queries in sub logarithmic time.

      • 24
        Plasmatic  commented on April 28, 2018, 5:02 a.m.

        is it the disjoint set thingy?