Editorial for Contest Area

First of all let's look into the important part of the problem. We will find that the room is connected by some directed path and the entire rooms and paths together can be constructed as a graph with nodes and edges. So we can assume the rooms as the nodes and the one directional path are edges of the graph.

Now, if we observe the characteristics of the graph, we can find, each two members of a team can communicate and they can go from one's room to another.

It means, there is a path between all pairs of rooms that are used by the members of the same team. From the information we can say, the rooms used by a team are strongly connected. But any two rooms from different teams are not strongly connected, though there may exist a path between the two rooms. If we can find who are strongly connected we can say that they are from the same team, and we can easily mark them using Strongly Connected Component algorithm. Then for each query we will find if participant a and b are from the same team.


    85% Solution Ratio

    MustangEarliest, 1M ago

    prodip_bsmrstuFastest, 0.1s

    RobinHood3082Lightest, 12 MB

    NirjhorShortest, 737B