## DMOPC '15 Contest 3 P4 - Contagion

View as PDF

Points:12 (partial)
Time limit:2.0s
PyPy 210.0s
PyPy 310.0s
Memory limit:128M
PyPy 2256M
PyPy 3256M
Author:

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 countries numbered through , represented by points on a 2-D coordinate plane. Country is located at integral coordinates .

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 is located at and country is located at , it will take hours for country to be infected after the initial infection of country . The source of the breakout, country , is infected at the -th hour.

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

How many countries will be infected after hours?

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

#### Constraints

,

,

,

,

,

,

Note: For PyPy 2 and PyPy 3 and Haskell, the time limit is s and the memory limit is M.

#### Input Specification

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

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

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

The next line will contain , the number of queries.

The next 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 hours, the pathogen has not yet spread from its source, therefore answer is . After hours, country is infected. After hours, country is also infected. At hours, the pathogen has spread from country to country .

• root
commented on June 17, 2017

Please, for the sanity of DMOJ programmers, allow submissions that don't pass the sample case to run on the other batches. It's a nightmare debugging an RTE with no output.

• aurpine
commented on Jan. 5, 2016
RTE

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

• cheesecake
commented on Jan. 5, 2016 edited

It's very expensive memory-wise to maintain a priority queue of up to 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.

• bobhob314
commented on Jan. 5, 2016 edit 6

It's probably because you're initializing a long long array of elements, although I didn't look at your code in detail enough to be sure.

Since a long long takes up bits of memory and you're allocating of them, that means you're using up bits, or bytes, or . 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!

• jlsajfj
commented on March 29, 2016

Bruce or Jason's help lol

• cheesecake
commented on Dec. 19, 2015
Hint for Python

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

• minecraftyugi
commented on Dec. 18, 2015
Only PHP judge available?

I'm not sure if this is a bug or something, but the code can only be submitted in php

• Xyene
commented on Dec. 18, 2015

It's fixed now; these issues occur sometimes when we update the judges.