# BOI 2016, day 1

 Start: 2016-05-12 09:00:00 End: 2016-05-12 14:00:00

CSES - BOI 2016, day 1 - Results
History
2016-05-12 13:42:410
2016-05-12 12:58:080
 Task: Park Sender: Coder7 Submission time: 2016-05-12 13:42:41 Language: C++ Status: READY Score: 0

## Feedback

 group verdict score #1 TIME LIMIT EXCEEDED 0 #2 WRONG ANSWER 0 #3 TIME LIMIT EXCEEDED 0

## Code

```#include <iostream>
#include <cmath>
#define INF 1000000009

using namespace std;

int n, m;//trees, people
int w, h;//weight, height
int x[2007], y[2007], r[2007];
int k, e;
int DIF[2007][2007];

int D[5][5];
int col[2007];

void DFS(int s1, int u1);
int DC(int min, int max, int a, int b);
bool reachable(int s, int u, int a1, int b1);

int main(){

cin >> n >> m;
cin >> w >> h;
//input
for(int i = 5; i < n+5; i++){
cin >> x[i] >> y[i] >> r[i];
}
//creating graph
for(int i = 1; i < 5; i++){
for(int j = 1; j < 5; j++){
DIF[i][j]=INF;
}
for(int j = 5; j < n+5; j++){
if(i==1){
DIF[i][j]=y[j]-r[j];
}else if(i==2){
DIF[i][j]=w-x[j]-r[j];
}else if(i == 3){
DIF[i][j]=h-y[j]-r[j];
}else{
DIF[i][j]=x[j]-r[j];
}
DIF[j][i]=DIF[i][j];
}
}

for(int i = 5; i < n+5; i++){
for(int j = i+1; j < n+5; j++){
int r7 = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
DIF[i][j]=r7-r[i]-r[j];
DIF[j][i]=DIF[i][j];
}
}

//getting shortest possible distanc for each of them
for(int i = 1; i < 4; i++){
for(int j = i+1; j < 5; j++){
D[i][j]=DC(0, 1000000009, i, j);
D[j][i]=D[i][j];
//cout << i << "::" << j << "=>" << D[i][j] << endl;
}
}

//output
for(int i = 1; i < m+1; i++){
cin >> k >> e;
bool v[5] = {1, 1, 1, 1, 1};
k = 2*k;
if(e == 1){
if(D[1][4]<k){
v[2]=v[3]=v[4]=0;
}
if(D[1][3]<k){
v[2]=v[3]=0;
}
if(D[1][2]<k){
v[2]=0;
}
if(D[2][3]<k){
v[3]=0;
}
if(D[2][4]<k){
v[3]=v[4]=0;
}
if(D[3][4]<k){
v[4]=0;
}
}else if(e == 2){
if(D[1][4]<k){
v[1]=0;
}
if(D[1][3]<k){
v[1]=v[4]=0;
}
if(D[1][2]<k){
v[1]=v[3]=v[4]=0;
}
if(D[2][3]<k){
v[3]=0;
}
if(D[2][4]<k){
v[3]=v[4]=0;
}
if(D[3][4]<k){
v[4]=0;
}
}else if(e == 3){
if(D[1][4]<k){
v[1]=0;
}
if(D[1][3]<k){
v[1]=v[4]=0;
}
if(D[1][2]<k){
v[2]=0;
}
if(D[2][3]<k){
v[1]=v[2]=v[4]=0;
}
if(D[2][4]<k){
v[1]=v[2]=0;
}
if(D[3][4]<k){
v[4]=0;
}
}else{
if(D[1][4]<k){
v[1]=0;
}
if(D[1][3]<k){
v[2]=v[3]=0;
}
if(D[1][2]<k){
v[2]=0;
}
if(D[2][3]<k){
v[3]=0;
}
if(D[2][4]<k){
v[1]=v[2]=0;
}
if(D[3][4]<k){
v[1]=v[2]=v[3]=0;
}
}
for(int b9 = 1; b9 < 5; b9++){
if(v[b9]){
cout << b9;
}
}
cout << endl;
}

return 0;
}

int DC(int min, int max, int a, int b){
if(max == min){
return max;
}
int mid = (min+max)/2;
if(reachable(a, mid, a, b)){
return DC(min, mid, a, b);
}else{
return DC(mid+1, max, a, b);
}
}

bool reachable(int s, int u, int a1, int b1){
for(int i = 1; i < n+5; i++){
col[i]=false;
}
col[s]=true;
DFS(s, u);
if(col[b1]==true){
return true;
}
return false;
}

void DFS(int s1, int u1){
for(int i = 1; i < n+5; i++){
if(DIF[s1][i]<=u1 && col[i]==false){
col[i]=true;
DFS(i, u1);
}
}
}

```

## Test details

### Test 1

Group: 1

Verdict: TIME LIMIT EXCEEDED

input
`2000 1979513360 951064428919546609 316314580 2377936339446741 628130423 4125204121572058 270524668 5636432...`
view   save

correct output
`3`
view   save

user output
(empty)

### Test 2

Group: 1

Verdict: TIME LIMIT EXCEEDED

input
`2000 1991199014 920833466230700794 888996817 6050635481388637 266963369 8990139388128678 193075342 6392873...`
view   save

correct output
`123`
view   save

user output
(empty)

### Test 3

Group: 1

input
`2000 1912908727 909993663497818433 252740213 130264819445396 162424624 2590054851436472 463371747 1783777...`
view   save

correct output
`13`
view   save

user output
`1`
view   save

### Test 4

Group: 1

input
`2000 1999389891 924955261154253387 891000940 607638259202899 565427474 8676367123280124 461618875 16605...`
view   save

correct output
`124`
view   save

user output
`2`
view   save

### Test 5

Group: 1

input
`2000 1954679508 995423791114486161 258621130 1651405236582339 590299172 7669288408723654 553042386 13639...`
view   save

correct output
`1234`
view   save

user output
`3`
view   save

### Test 6

Group: 1

Verdict: TIME LIMIT EXCEEDED

input
`2000 1937290370 990023490548183238 668272337 694039917490037 355711568 6267836464677420 473577708 1705970...`
view   save

correct output
`234`
view   save

user output
(empty)

### Test 7

Group: 1

Verdict: ACCEPTED

input
`2000 11000000000 1000000000532933 500000000 1813051121313 500000000 1327991349788 500000000 95636...`
view   save

correct output
`12`
view   save

user output
`12`
view   save

### Test 8

Group: 1

input
`2000 11000000000 1000000000999214206 500000000 32714999000173 500000000 123669996825328 500000000 13444...`
view   save

correct output
`1234`
view   save

user output
`12`
view   save

### Test 9

Group: 1

input
`8 11000000000 1000000000200000000 384529926 2459575400000000 269059852 2459575400000000 499999960 2459575...`
view   save

correct output
`134`
view   save

user output
`3`
view   save

### Test 10

Group: 1

input
`8 11000000000 1000000000200000000 384529926 2192968400000000 269059852 2192968400000000 499999960 2192968...`
view   save

correct output
`34`
view   save

user output
`3`
view   save

### Test 11

Group: 2

input
`200 100000993985849 949873837619688070 593376074 2640100451123815 780993228 13183641266929658 843234344 18993732...`
view   save

correct output
`12412341234241...`
view   save

user output
`1341221...`
view   save

### Test 12

Group: 2

input
`200 100000982434756 609937936695001046 491087928 16349486790013019 427021425 18691445123384937 443241449 12436568...`
view   save

correct output
`21123412341...`
view   save

user output
`21321...`
view   save

### Test 13

Group: 2

input
`200 100000252174733 97834774084976972 739235003 3453165183216957 798073359 495893754932300 631165519 2427103...`
view   save

correct output
`12341234123441234...`
view   save

user output
`42123443...`
view   save

### Test 14

Group: 2

input
`200 100000962079396 954653252377813916 356435724 6114019573684958 814097817 285471018344298 745997487 1106881...`
view   save

correct output
`1234312341231234...`
view   save

user output
`12343323...`
view   save

### Test 15

Group: 2

input
`200 100000983619508 94792366648721169 702938953 450395711039974 141619954 13074117533030306 254919890 19245304...`
view   save

correct output
`1313123424...`
view   save

user output
`31124...`
view   save

### Test 16

Group: 2

input
`200 1000001000000000 1000000000997539459 500000000 1239023991535567 500000000 1287423137985 500000000 15999...`
view   save

correct output
`1234123412341234...`
view   save

user output
`123412341234...`
view   save

### Test 17

Group: 2

input
`8 1000001000000000 1000000000200000000 384529926 2147940400000000 269059852 2147940400000000 499999960 2147940...`
view   save

correct output
`32412343...`
view   save

user output
`32433...`
view   save

### Test 18

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`2000 100000994458630 910261182228672329 565536439 6062123865578660 350406456 1902914658300836 250167973 4318414...`
view   save

correct output
`1234121234121234...`
view   save

user output
(empty)

### Test 19

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`2000 100000515185242 944723489362533601 102695020 1535335367129302 105681887 104412878363007 423585007 8499033...`
view   save

correct output
`12342131234...`
view   save

user output
(empty)

### Test 20

Group: 3

input
`2000 100000943877407 973718583554730247 145643422 5156712450379716 747719842 5552798359822323 539661121 4496376...`
view   save

correct output
`123414231234...`
view   save

user output
`31424...`
view   save

### Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`2000 100000955646071 38681295878813697 210798005 2565719428648058 66546609 369988244149147 6888916 1802358...`
view   save

correct output
`12344123441234...`
view   save

user output
(empty)

### Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`2000 100000919439951 944456830893635539 257036972 4101254450766196 632933839 341679257291728 805137182 2282993...`
view   save

correct output
`123424123412341234...`
view   save

user output
(empty)

### Test 23

Group: 3

input
`2000 1000001000000000 1000000000999824177 500000000 111947345628 500000000 165362999366104 500000000 16658...`
view   save

correct output
`1234123412341212...`
view   save

user output
`34123412341212...`
view   save

### Test 24

Group: 3

`8 1000001000000000 1000000000200000000 384529926 2181527400000000 269059852 2181527400000000 499999960 2181527...`
`12341312341234...`
`21314...`