DMOPC '15 Contest 3 P4 - Contagion

View as PDF
Submit solution
Points: 12 (partial)
Time limit: 1.0s
Memory limit: 128M
Author:
cheesecake
Problem type

cheesecake works part-time at the Centre for Disease Control and Prevention (CDC), where he researches the spread of diseases. An unknown pathogen has just broken out and cheesecake is determined to save the world!

The CDC's model of the world consists of N countries numbered 1 through N, represented by points on a 2-D coordinate plane. Country i is located at integral coordinates (x_i, y_i).

Through extensive research, cheesecake has determined a vital piece of information: the time in hours it takes for the pathogen to spread from one country to another is equal to the square of the distance between the two countries. For example, if country A is located at (0,0) and country B is located at (2,3), it will take 13 hours for country B to be infected after the initial infection of country A. The source of the breakout, country X (1 \le X \le N), is infected at the 0-th hour.

In order to take preventative measures, cheesecake has been tasked with projecting the rate of infection. Specifically, he has to answer Q queries of the following form:

How many countries will be infected after Q_i hours?

Unfortunately, cheesecake isn't taking data management this semester, so he's at a total loss. Help him save the world!

Constraints

Subtask 1 [20%]

1 \le N \le 100, 0 \le x_i, y_i \le 100

1 \le Q \le 10, 0 \le Q_i \le 10^5

Subtask 2 [30%]

1 \le N \le 1000, 0 \le x_i, y_i \le 10^4

1 \le Q \le 1000, 0 \le Q_i \le 10^9

Subtask 3 [50%]

1 \le N \le 3000, 0 \le x_i, y_i \le 10^6

1 \le Q \le 10^6, 0 \le Q_i \le 10^{14}

Input Specification

The first line of input will contain N, the number of countries.

The next N lines will contain x_i and y_i, the coordinates of the i-th country, it is guaranteed that no two countries will have the same coordinates.

The next line will contain X, the source of the breakout.

The next line will contain Q, the number of queries.

The next Q lines will each contain a query.

Output Specification

For each query, output the answer on a new line.

Sample Input

4
2 2
0 3
5 1
4 0
1
4
8
10
4
7

Sample Output

3
4
1
2

Explanation for Sample Output

After 4 hours, the pathogen has not yet spread from its source, therefore the answer is 1. After 7 hours, country 2 is infected. After 8 hours, country 4 is also infected. At 10 hours, the pathogen has spread from country 4 to country 3.

Comments


  • 0
    pblpbl  commented on Feb. 29, 2020, 5:25 a.m.

    Assuming the first test case is the test case, my clipped output does not match my output in the compiler. My program prints out "3 4 1 2" (on different lines) but the clipped output says "1 1 1 1" (on different lines).


    • 1
      wleung_bvg  commented on Feb. 29, 2020, 5:29 a.m.

      Your code has undefined behaviour. Your visited array needs to be initialized to a value, or else it will take whatever garbage values are currently stored at that memory address.


  • 3
    albertlai431  commented on Dec. 4, 2017, 2:15 a.m.

    For the explanation for sample output, shouldn't the time it takes to get to country 2 be 5 hours, not 7 hours?


    • 0
      eric574  commented on Dec. 4, 2017, 3:12 a.m. ← edited

      No, it's simply referring to the query, since the explanation is not written in chronological order


  • -1
    Pleedoh  commented on Aug. 20, 2017, 4:54 a.m. ← edit 3

    EDIT Make sure you use correct types!


  • 0
    aurpine  commented on Jan. 6, 2016, 2:31 a.m.

    Why are so many people (including myself) getting runtime error? :'(


    • 0
      cheesecake  commented on Jan. 6, 2016, 3:09 a.m. ← edited

      It's very expensive memory-wise to maintain a priority queue of up to \dfrac{N\times(N-1)}{2} edges. Even if I raise the memory limit to 1 GB, your solution will TLE. The editorial might help you.

      Edit: I think it depends on which judge your submission was run on. 64-bit judges will give you RTE and 32-bit judges will give you TLE.


    • -1
      bobhob314  commented on Jan. 6, 2016, 2:33 a.m. ← edit 6

      It's probably because you're initializing a long long array of 9*10^6 elements, although I didn't look at your code in detail enough to be 100\% sure.

      Since a long long takes up 64 bits of memory and you're allocating 9*10^6 of them, that means you're using up 576,000,000 bits, or 72,000,000 bytes, or 72MB. That should technically pass the memory limit, maybe? But you'd be cutting it close with all of your other variables and arrays.

      Be aware that if you wanted mathematical rigor, you should have specifically asked for Bruce or Jason's help. :)

      Anyway, that might be why, or maybe I'm totally off. Cheers!


      • 0
        jlsajfj  commented on March 30, 2016, 12:27 a.m.

        Bruce or Jason's help lol


  • 3
    cheesecake  commented on Dec. 19, 2015, 6:44 p.m.

    If you're getting TLE on Python, try using multiplication instead of power.