## DMPG '17 S2 - Anime Conventions

View as PDF

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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 actions:

• A x y: Build a road between cities and .
• Q x y: Check if cities and 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, , and , the number of cities and queries, respectively.
The next lines each have a query. It is guaranteed that .

For of points, .

#### Output Specification

For each query in the form Q x y, print Y if you can travel from city to city . 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

Y
Y
N

#### Explanation

For the first query, the king can travel along the following path:

For the second query, the king can travel along the following path:

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

• commented on July 29, 2020, 1:14 p.m.

can somebody give some pointers for my code

• commented on July 29, 2020, 3:51 p.m.
• commented on July 30, 2020, 6:21 p.m.

bruh

• commented on Nov. 27, 2019, 11:40 a.m.

for each Q, add new edge if x and y is connected

• commented on May 17, 2017, 4:40 p.m.

Any optimization tips for my program?

• commented on May 17, 2017, 6: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.

• commented on April 28, 2018, 1:02 a.m.

is it the disjoint set thingy?