DMPG '17 S2 - Anime Conventions - Olympiads Online Judge

DMPG '17 S2 - Anime Conventions

View as PDF

Submit solution

All submissions

Best submissions

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:

Kirito

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$ ~Q~ actions:

A x y: Build a road between cities $x$ ~x~ and $y$ ~y~.
Q x y: Check if cities $x$ ~x~ and $y$ ~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$ ~N~, and $Q$ ~Q~ $(2 \le N \le 10^5; 1 \le Q \le 10^5)$ ~(2 \le N \le 10^5; 1 \le Q \le 10^5)~, the number of cities and queries, respectively.
The next $Q$ ~Q~ lines each have a query. It is guaranteed that $x \ne y; 1 \le x, y \le N$ ~x \ne y; 1 \le x, y \le N~.

For $30\%$ ~30\%~ of points, $1 \le N, Q \le 1\,000$ ~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$ ~x~ to city $y$ ~y~. Otherwise, print N.

Sample Input

Sample Output

Y
Y
N

Explanation

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

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

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

Comments

7

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

can somebody give some pointers for my code

59

d commented on July 29, 2020, 7:51 p.m.

https://xkcd.com/138/

23

jerry0101 commented on July 30, 2020, 10:21 p.m.

bruh

1

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

Any optimization tips for my program?

24

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.

23

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

is it the disjoint set thingy?