Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Shhh! Don't Tell!

By TarifEzaz · Limits 3s, 1.0 GB

The Bad guys are using the social media to spread their malicious messages to the mass. They have collected the information of interactions between a large group of people. By using these information, they want to spread rumors that would help them to fulfill their evil means.

Formally, Bad guys have created a list of E interactions, each in the format (U V T). Each of these interactions suggests that person U and person V will have an interaction in time T.

Now, you are on the side of Good guys and want to take these bad people down. In order to investigate how ordinary people may be affected, you want to run a simulation on the data of interactions. Concretely, you want to know if a person A generates a rumor in time X, will another person B be informed about that rumor on or before time Y? The person B will only be aware about the rumor from person A, if there is a sequence of interactions that starts from person A and ends at person B and follows a chronological order within the time limit from X to Y inclusive. Chronological means starting with the earliest and following the order in which the events occurred.

Given the list of possible interactions and the list of queries, you have to answer for each query, whether person B can get the rumor generated by person A.


The first line of the input contains a number E ( 1≤ E ≤ 105 ), the number of interactions.

The following E lines will be in the format U V T ( 1 ≤ U, V ≤ 1000, 1 ≤ T ≤ 109 ), indicating an interaction between person U and V in time T.

The next line will have an integer Q ( ≤ 1000 ), the number of queries.

The next Q lines will be in the following format A X B Y ( 1≤ A, B ≤1000, 1≤ X, Y ≤109, X ≤ Y ), asking whether a rumor generated from person A at time X, can be transferred to the person B within time Y.


For each query, print Yes, if the rumor can be transferred or No otherwise.


1 2 1
2 3 2
1 1 3 2



57% Solution Ratio

Tarik.amtolyEarliest, Oct '17

BarbariansFastest, 0.5s

IshrakLightest, 2.4 MB

experimenterShortest, 1105B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.