## DMPG '15 S4 - Signal Hill

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
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 a certain 2D kingdom, there exist beacons, numbered .

Since they were built at different times during the kingdom's history, they were not all constructed under the same specifications. As such, certain beacons may be brighter than others. A beacon 's range is defined as the radius around the beacon's location inside which the light from the beacon is visible.

Initially, all beacons are unlit. In the case of an invasion, a beacon will be lit, and the light from it will signal all beacons within its range (including beacons just barely within its range) to light as well. In this way, news of the invasion will propagate throughout the entire kingdom efficiently.

Or at least, that's what's supposed to happen. However, due to the haphazard way in which the beacon network was built, it may not function as intended. That is, some beacons or groups of beacons may be separated from each other, so that a signal may not be physically able propagate through the entire network.

As part of a repairing initiative, Ironwood has been tasked with answering queries of the form , — whether beacon will ever be lit when beacon is lit.

#### Constraints

##### Subtask 2 [20%]

For all cases, and .

#### Input Specification

The first line of input will contain two space-separated integers and .
For the next lines, line will represent beacon , and will contain three space-separated positive integers: , , and . The value of these integers will not exceed .
Finally, the next lines will each contain two space-separated integers representing a query: and .

#### Output Specification

For each query, one line containing YES if the two beacons are connected, or NO otherwise.

#### Sample Input

2 2
1 1 5
4 1 1
1 2
2 1

#### Sample Output

YES
NO

## Comments

• commented on Dec. 20, 2017, 5:49 p.m.

Keep on TLE int on test case 7

• commented on July 31, 2017, 5:30 p.m.

How can I speed up my code? On some judges I TLE test cases 8 and 10, on others I TLE only test case 10. I've tried everything I used to optimize my BFS in Pursuit of Knowledge, but I can't get the last test case without MLE'ing.

• commented on July 31, 2017, 6:11 p.m. edit 2

Since the number of queries is at most 500 (the max number of vertices), you can do individual searches for each query instead of pre-computing and storing them in a 2-d array. This also means you can terminate bfs as soon as you find a path.

• commented on July 31, 2017, 6:21 p.m.

That is a rather unexpected solution. Thanks for your help!

• commented on May 6, 2017, 4:44 p.m.

Why do I keep getting only 3 of the 10 test cases?

• commented on May 6, 2017, 10:27 p.m. edited

Your code checks if 2 beacons are within a certain radius of each other, which is different than the question. One beacon can activate another through a chain. Let's say beacon C is within dist R of beacon A, and beacon B is within dist R of beacon C, but beacon B is not within dist R of beacon A. Beacon B will still be lit through the chain (A -> C -> B).

• commented on June 9, 2015, 7:21 p.m.

My code seems to compile fine on my computer but i get compilation error here.

• commented on June 9, 2015, 8:29 p.m.

you forgot to put

#include<algorithm>

in the beginning of your code

• commented on June 10, 2015, 7:38 p.m.

Wait how do you guys know what code other people submitted? Can people see what code I submit?

• commented on June 10, 2015, 7:40 p.m. edited

If you have solved a problem, you can view all submissions made on said problem.

Edit: So yes, in re your second question, people can see what code you submit.

• commented on June 10, 2015, 7:44 p.m.

Oh sweet, I didn't even know about that. Thank you!

• commented on June 11, 2015, 11:19 a.m.

Bunny, do you have a youtube channel? I swear I watched one of your videos before!

• commented on July 28, 2015, 11:02 a.m.

I actually do have a YouTube channel and I have around 450,000 views and it's about programming & software (mostly) :P

• commented on July 28, 2015, 5:30 p.m.
• commented on July 28, 2015, 5:49 p.m.

Wow I just tried to find myself using MathBunny to no avail ... I wonder how you found out LOL. Some detective work indeed

• commented on July 28, 2015, 5:48 p.m.

You guys pass, A+ detective work (y)

But yeah that's the right channel, bobhob was pretty close too

• commented on April 16, 2016, 9:07 a.m.

so many "re"s lol

• commented on May 13, 2017, 3:16 p.m.

lol ikr

• commented on Feb. 16, 2019, 3:16 p.m.

lmao nice

• commented on July 28, 2015, 1:51 p.m.

Link?

• commented on June 11, 2015, 3:23 p.m.
• commented on July 28, 2015, 11:06 a.m.

Hahaha