DMPG '15 S4 - Signal Hill

View as PDF
Submit solution
Points: 10
Time limit: 1.0s
Memory limit: 64M
Author:
Xyene
Problem type

In a certain 2D kingdom, there exist B beacons, numbered 1 \dots B.

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 i's range r_i is defined as the radius around the beacon's location (x_i, y_i) 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 to propagate through the entire network.

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

Constraints

For all cases, 2 \le B \le 500 and a \ne b.

Subtask 1 [80%]
  • 1 \le Q \le 100
Subtask 2 [20%]
  • 1 \le Q \le 500

Input Specification

The first line of input will contain two space-separated integers B and Q.
For the next B lines, line i will represent beacon i, and will contain three space-separated positive integers: x_i, y_i, and r_i. The value of these integers will not exceed 10\,000.
Finally, the next Q lines will each contain two space-separated integers representing a query: a and b.

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


  • -3
    aeternalis1  commented on July 31, 2017, 9: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.


    • 2
      wleung_bvg  commented on July 31, 2017, 10: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.


      • -2
        aeternalis1  commented on July 31, 2017, 10:21 p.m.

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


  • 0
    will31415  commented on May 6, 2017, 8:44 p.m.

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


    • 0
      wleung_bvg  commented on May 7, 2017, 2:27 a.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).


  • 0
    boogieman  commented on June 9, 2015, 11:21 p.m.

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


    • 0
      kobortor  commented on June 10, 2015, 12:29 a.m.

      you forgot to put

      #include<algorithm>

      in the beginning of your code


      • 0
        MathBunny  commented on June 10, 2015, 11:38 p.m.

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


        • 4
          bobhob314  commented on June 10, 2015, 11: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.


          • 0
            MathBunny  commented on June 10, 2015, 11:44 p.m.

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


            • 2
              omaewamoushindeiru  commented on June 11, 2015, 3:19 p.m.

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


              • 0
                MathBunny  commented on July 28, 2015, 3:02 p.m.

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


                • 2
                  Xyene  commented on July 28, 2015, 9:30 p.m.

                  Detective skills activate!


                  • 0
                    MathBunny  commented on July 28, 2015, 9: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


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

                    You guys pass, A+ detective work (y)

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


                    • 1
                      jlsajfj  commented on April 16, 2016, 1:07 p.m.

                      so many "re"s lol


                      • 1
                        howardt12345  commented on May 13, 2017, 7:16 p.m.

                        lol ikr


                        • 1
                          Jerry_Gu  commented on Feb. 16, 2019, 8:16 p.m.

                          lmao nice


              • 4
                bobhob314  commented on June 11, 2015, 7:23 p.m.

                this?


                • 0
                  MathBunny  commented on July 28, 2015, 3:06 p.m.

                  Hahaha