Code Submission Evaluation System Login

BOI 2016, day 1

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

Tasks | Scoreboard | Statistics


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

groupverdictscore
#1TIME LIMIT EXCEEDED0
#2WRONG ANSWER0
#3TIME LIMIT EXCEEDED0

Test results

testverdicttime (s)group
#1TIME LIMIT EXCEEDED-- / 2.501details
#2TIME LIMIT EXCEEDED-- / 2.501details
#3WRONG ANSWER2.46 / 2.501details
#4WRONG ANSWER2.39 / 2.501details
#5WRONG ANSWER2.49 / 2.501details
#6TIME LIMIT EXCEEDED-- / 2.501details
#7ACCEPTED2.22 / 2.501details
#8WRONG ANSWER1.68 / 2.501details
#9WRONG ANSWER0.04 / 2.501details
#10WRONG ANSWER0.05 / 2.501details
#11WRONG ANSWER0.18 / 2.502details
#12WRONG ANSWER0.19 / 2.502details
#13WRONG ANSWER0.18 / 2.502details
#14WRONG ANSWER0.19 / 2.502details
#15WRONG ANSWER0.19 / 2.502details
#16WRONG ANSWER0.18 / 2.502details
#17WRONG ANSWER0.17 / 2.502details
#18TIME LIMIT EXCEEDED-- / 2.503details
#19TIME LIMIT EXCEEDED-- / 2.503details
#20WRONG ANSWER2.47 / 2.503details
#21TIME LIMIT EXCEEDED-- / 2.503details
#22TIME LIMIT EXCEEDED-- / 2.503details
#23WRONG ANSWER2.17 / 2.503details
#24WRONG ANSWER0.17 / 2.503details

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 1
979513360 951064428
919546609 316314580 2377936
339446741 628130423 4125204
121572058 270524668 5636432
...
view   save

correct output
3

view   save

user output
(empty)

Test 2

Group: 1

Verdict: TIME LIMIT EXCEEDED

input
2000 1
991199014 920833466
230700794 888996817 6050635
481388637 266963369 8990139
388128678 193075342 6392873
...
view   save

correct output
123

view   save

user output
(empty)

Test 3

Group: 1

Verdict: WRONG ANSWER

input
2000 1
912908727 909993663
497818433 252740213 1302648
19445396 162424624 2590054
851436472 463371747 1783777
...
view   save

correct output
13

view   save

user output
1

view   save

Test 4

Group: 1

Verdict: WRONG ANSWER

input
2000 1
999389891 924955261
154253387 891000940 6076382
59202899 565427474 8676367
123280124 461618875 16605
...
view   save

correct output
124

view   save

user output
2

view   save

Test 5

Group: 1

Verdict: WRONG ANSWER

input
2000 1
954679508 995423791
114486161 258621130 1651405
236582339 590299172 7669288
408723654 553042386 13639
...
view   save

correct output
1234

view   save

user output
3

view   save

Test 6

Group: 1

Verdict: TIME LIMIT EXCEEDED

input
2000 1
937290370 990023490
548183238 668272337 6940399
17490037 355711568 6267836
464677420 473577708 1705970
...
view   save

correct output
234

view   save

user output
(empty)

Test 7

Group: 1

Verdict: ACCEPTED

input
2000 1
1000000000 1000000000
532933 500000000 181305
1121313 500000000 132799
1349788 500000000 95636
...
view   save

correct output
12

view   save

user output
12

view   save

Test 8

Group: 1

Verdict: WRONG ANSWER

input
2000 1
1000000000 1000000000
999214206 500000000 32714
999000173 500000000 123669
996825328 500000000 13444
...
view   save

correct output
1234

view   save

user output
12

view   save

Test 9

Group: 1

Verdict: WRONG ANSWER

input
8 1
1000000000 1000000000
200000000 384529926 2459575
400000000 269059852 2459575
400000000 499999960 2459575
...
view   save

correct output
134

view   save

user output
3

view   save

Test 10

Group: 1

Verdict: WRONG ANSWER

input
8 1
1000000000 1000000000
200000000 384529926 2192968
400000000 269059852 2192968
400000000 499999960 2192968
...
view   save

correct output
34

view   save

user output
3

view   save

Test 11

Group: 2

Verdict: WRONG ANSWER

input
200 100000
993985849 949873837
619688070 593376074 26401004
51123815 780993228 13183641
266929658 843234344 18993732
...
view   save

correct output
124
1234
1234
24
1
...
view   save

user output
1
34
12
2
1
...
view   save

Test 12

Group: 2

Verdict: WRONG ANSWER

input
200 100000
982434756 609937936
695001046 491087928 16349486
790013019 427021425 18691445
123384937 443241449 12436568
...
view   save

correct output
2
1
1234
1234
1
...
view   save

user output
2
1
3
2
1
...
view   save

Test 13

Group: 2

Verdict: WRONG ANSWER

input
200 100000
252174733 978347740
84976972 739235003 3453165
183216957 798073359 4958937
54932300 631165519 2427103
...
view   save

correct output
1234
1234
1234
4
1234
...
view   save

user output
4
2
1234
4
3
...
view   save

Test 14

Group: 2

Verdict: WRONG ANSWER

input
200 100000
962079396 954653252
377813916 356435724 6114019
573684958 814097817 2854710
18344298 745997487 1106881
...
view   save

correct output
1234
3
1234
123
1234
...
view   save

user output
1234
3
3
2
3
...
view   save

Test 15

Group: 2

Verdict: WRONG ANSWER

input
200 100000
983619508 947923666
48721169 702938953 450395
711039974 141619954 13074117
533030306 254919890 19245304
...
view   save

correct output
13
13
1234
2
4
...
view   save

user output
3
1
1
2
4
...
view   save

Test 16

Group: 2

Verdict: WRONG ANSWER

input
200 100000
1000000000 1000000000
997539459 500000000 1239023
991535567 500000000 1287423
137985 500000000 15999
...
view   save

correct output
12
34
1234
1234
1234
...
view   save

user output
12
34
1234
12
34
...
view   save

Test 17

Group: 2

Verdict: WRONG ANSWER

input
8 100000
1000000000 1000000000
200000000 384529926 2147940
400000000 269059852 2147940
400000000 499999960 2147940
...
view   save

correct output
3
2
4
1234
3
...
view   save

user output
3
2
4
3
3
...
view   save

Test 18

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
2000 100000
994458630 910261182
228672329 565536439 6062123
865578660 350406456 1902914
658300836 250167973 4318414
...
view   save

correct output
1234
12
1234
12
1234
...
view   save

user output
(empty)

Test 19

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
2000 100000
515185242 944723489
362533601 102695020 1535335
367129302 105681887 1044128
78363007 423585007 8499033
...
view   save

correct output
1234
2
1
3
1234
...
view   save

user output
(empty)

Test 20

Group: 3

Verdict: WRONG ANSWER

input
2000 100000
943877407 973718583
554730247 145643422 5156712
450379716 747719842 5552798
359822323 539661121 4496376
...
view   save

correct output
1234
1
4
23
1234
...
view   save

user output
3
1
4
2
4
...
view   save

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
2000 100000
955646071 386812958
78813697 210798005 2565719
428648058 66546609 3699882
44149147 6888916 1802358
...
view   save

correct output
1234
4
1234
4
1234
...
view   save

user output
(empty)

Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
2000 100000
919439951 944456830
893635539 257036972 4101254
450766196 632933839 3416792
57291728 805137182 2282993
...
view   save

correct output
1234
24
1234
1234
1234
...
view   save

user output
(empty)

Test 23

Group: 3

Verdict: WRONG ANSWER

input
2000 100000
1000000000 1000000000
999824177 500000000 111947
345628 500000000 165362
999366104 500000000 16658
...
view   save

correct output
1234
1234
1234
12
12
...
view   save

user output
34
1234
1234
12
12
...
view   save

Test 24

Group: 3

Verdict: WRONG ANSWER

input
8 100000
1000000000 1000000000
200000000 384529926 2181527
400000000 269059852 2181527
400000000 499999960 2181527
...
view   save

correct output
1234
1
3
1234
1234
...
view   save

user output
2
1
3
1
4
...
view   save