CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Hämähäkit
Sender:
Submission time:2015-12-20 16:04:54 +0200
Language:C++
Status:READY
Result:20
Feedback
groupverdictscore
#1ACCEPTED20
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.06 s1details
#3ACCEPTED0.05 s1details
#4ACCEPTED0.06 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.05 s1details
#7ACCEPTED0.06 s1details
#8ACCEPTED0.04 s1details
#9ACCEPTED0.05 s1details
#10ACCEPTED0.05 s1details
#11ACCEPTED0.06 s1details
#12ACCEPTED0.06 s1details
#13ACCEPTED0.06 s1details
#14ACCEPTED0.06 s1details
#15ACCEPTED0.05 s1details
#16ACCEPTED0.06 s1details
#17ACCEPTED0.05 s1details
#18ACCEPTED0.05 s1details
#19ACCEPTED0.10 s1details
#20ACCEPTED0.06 s1details
#21ACCEPTED0.06 s1details
#22ACCEPTED0.06 s1details
#23ACCEPTED0.06 s2details
#24ACCEPTED0.06 s2details
#25ACCEPTED0.05 s2details
#26ACCEPTED0.05 s2details
#27ACCEPTED0.05 s2details
#28ACCEPTED0.06 s2details
#29ACCEPTED0.06 s2details
#30ACCEPTED0.05 s2details
#310.05 s2details
#32ACCEPTED0.05 s2details
#33ACCEPTED0.05 s2details
#34ACCEPTED0.05 s2details
#350.06 s2details
#36ACCEPTED0.07 s2details
#37ACCEPTED0.06 s2details
#38ACCEPTED0.05 s2details
#390.05 s2details
#40ACCEPTED0.06 s2details
#41ACCEPTED0.05 s2details
#42ACCEPTED0.06 s2details
#43ACCEPTED0.05 s2details
#44ACCEPTED0.06 s2details
#450.41 s3details
#46ACCEPTED0.43 s3details
#47ACCEPTED0.37 s3details
#48ACCEPTED0.38 s3details
#49ACCEPTED0.36 s3details
#500.38 s3details
#510.42 s3details
#520.46 s3details
#530.42 s3details
#54ACCEPTED0.46 s3details
#550.45 s3details
#56ACCEPTED0.31 s3details
#57ACCEPTED0.44 s3details
#580.35 s3details
#59ACCEPTED0.42 s3details
#600.46 s3details
#61ACCEPTED0.33 s3details
#62ACCEPTED0.28 s3details
#630.49 s3details
#640.42 s3details
#65ACCEPTED0.18 s3details
#66ACCEPTED0.20 s3details

Compiler report

input/code.cpp: In function 'int f(int, int)':
input/code.cpp:36:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[x].size(); ++i) {
                      ^
input/code.cpp: In function 'int main()':
input/code.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < alku.size(); ++i) {
                      ^

Code

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#define F first
#define S second
using namespace std;

const int MN = 1e5+100;
int n,m,w;
vector<int> v[MN];
int crd[MN][2];
vector<bool> used(MN);
int ed2, x2;
const double PI = atan(1)*4;
double getAngle(int a) {
    //y, x
    double lol = atan2(crd[ed2][1]-crd[x2][1], crd[ed2][0]-crd[x2][0]) 
    - atan2(crd[a][1]-crd[x2][1], crd[a][0] - crd[x2][0]);
    lol = fmod(lol, 2*PI);
    lol += 2*PI;
    lol = fmod(lol, 2*PI);
    return lol;
}
bool cmp(int a, int b) {
    return getAngle(a) > getAngle(b);
}
int f(int ed, int x) {
    used[x] = 1;
    if(crd[x][0] == w) {
        return 1;
    }
    ed2 = ed;
    x2 = x;
    sort(v[x].begin(), v[x].end(), cmp);
    for(int i = 0; i < v[x].size(); ++i) {
        int y = v[x][i];
        if(!used[y]) {
            if(f(0, y)) return 1;
        }
    }
    return 0;
}
int main() {
    cin>>n>>m>>w;
    vector<pair<int, int> > alku, loppu;
    for(int i = 1; i <= n; ++i) {
        cin>>crd[i][0]>>crd[i][1];
        if(crd[i][0] == 0) alku.push_back({crd[i][1], i});
        if(crd[i][0] == w) loppu.push_back({crd[i][1], i});
    }
    crd[0][0] = -100;
    crd[0][1] = 0;
    sort(alku.begin(), alku.end());
    sort(loppu.begin(), loppu.end());
    for(int i = 0; i < m; ++i) {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int ans = 0;
    for(int i = 0; i < alku.size(); ++i) {
        if(!used[alku[i].S]) {
            if(f(0, alku[i].S)) ++ans;
        }
    }
    cout<<ans<<'\n';

}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10 17 1000000000
0 704856741
392413116 918234840
1000000000 731311135
1000000000 593757560
...

correct output
2

user output
2

Test 2

Group: 1

Verdict: ACCEPTED

input
10 17 794478484
0 37330414
0 259743949
0 531540654
0 778009211
...

correct output
1

user output
1

Test 3

Group: 1

Verdict: ACCEPTED

input
10 11 1000000000
1000000000 585128146
409193536 138134881
1000000000 494514146
308873435 315049323
...

correct output
2

user output
2

Test 4

Group: 1

Verdict: ACCEPTED

input
10 11 763531579
706445536 122850333
49164964 345223962
614457966 287408209
0 485829504
...

correct output
1

user output
1

Test 5

Group: 1

Verdict: ACCEPTED

input
10 18 1000000000
0 571227976
680761339 89607758
567992019 983903736
1000000000 474229512
...

correct output
2

user output
2

Test 6

Group: 1

Verdict: ACCEPTED

input
10 12 1000000000
313957685 818603188
387010958 567539413
1000000000 645615315
0 306911040
...

correct output
1

user output
1

Test 7

Group: 1

Verdict: ACCEPTED

input
10 13 571768693
0 55639447
571768693 405808386
288064339 140154072
424336596 489713815
...

correct output
0

user output
0

Test 8

Group: 1

Verdict: ACCEPTED

input
10 15 252362123
252362123 46382426
0 85132125
106811510 205398385
252362123 14519798
...

correct output
3

user output
3

Test 9

Group: 1

Verdict: ACCEPTED

input
10 18 1000000000
1000000000 919748180
0 471287453
386346932 725873235
20659927 232493946
...

correct output
1

user output
1

Test 10

Group: 1

Verdict: ACCEPTED

input
10 9 258137528
0 24798758
0 45922587
0 85319490
0 98277912
...

correct output
1

user output
1

Test 11

Group: 1

Verdict: ACCEPTED

input
10 10 553341255
417718587 444092326
506740637 249293506
0 360571774
270242038 513274782
...

correct output
1

user output
1

Test 12

Group: 1

Verdict: ACCEPTED

input
10 13 537309475
0 18430076
236008570 57914446
11154919 299393928
537309475 431426728
...

correct output
1

user output
1

Test 13

Group: 1

Verdict: ACCEPTED

input
10 9 781170500
781170500 372221421
90241429 590664765
52599719 265735624
0 500090360
...

correct output
1

user output
1

Test 14

Group: 1

Verdict: ACCEPTED

input
10 13 554169329
307219822 214362851
451885757 315093106
554169329 311139750
461903138 65696211
...

correct output
1

user output
1

Test 15

Group: 1

Verdict: ACCEPTED

input
10 18 213091754
156252421 25289594
213091754 137942481
205106954 8433370
52929600 129746959
...

correct output
1

user output
1

Test 16

Group: 1

Verdict: ACCEPTED

input
10 16 1000000000
1000000000 15138020
1000000000 126255051
849982729 966647807
1000000000 179010211
...

correct output
2

user output
2

Test 17

Group: 1

Verdict: ACCEPTED

input
10 20 1000000000
0 37647064
645647844 616703296
1000000000 786225442
182294700 952637957
...

correct output
3

user output
3

Test 18

Group: 1

Verdict: ACCEPTED

input
10 9 1000000000
0 692104680
1000000000 324478913
570249295 756617314
1000000000 582287428
...

correct output
2

user output
2

Test 19

Group: 1

Verdict: ACCEPTED

input
10 11 63915067
63915067 51389241
63915067 49586349
0 35193293
24279585 1742566
...

correct output
2

user output
2

Test 20

Group: 1

Verdict: ACCEPTED

input
10 9 820808114
434538241 790319655
820808114 362563661
762893006 10045535
185317888 680396420
...

correct output
1

user output
1

Test 21

Group: 1

Verdict: ACCEPTED

input
10 9 9
0 0
1 0
2 0
3 0
...

correct output
1

user output
1

Test 22

Group: 1

Verdict: ACCEPTED

input
10 9 1
0 0
1 1
0 2
1 3
...

correct output
5

user output
5

Test 23

Group: 2

Verdict: ACCEPTED

input
100 141 1000000000
68950345 288564348
0 96838032
185212952 386765864
116363878 810049498
...

correct output
5

user output
5

Test 24

Group: 2

Verdict: ACCEPTED

input
100 200 146097178
82666528 16373778
144674595 112106116
0 76994783
0 72029869
...

correct output
5

user output
5

Test 25

Group: 2

Verdict: ACCEPTED

input
100 200 154411254
65416084 72275512
89088641 67141418
21521539 130194125
95737402 140628842
...

correct output
2

user output
2

Test 26

Group: 2

Verdict: ACCEPTED

input
100 200 1000000000
137368094 831215834
1000000000 886503884
0 372336581
302500531 764813659
...

correct output
5

user output
5

Test 27

Group: 2

Verdict: ACCEPTED

input
100 200 308982367
83698736 126746838
211360400 142287535
114968978 89172722
75917652 306159625
...

correct output
2

user output
2

Test 28

Group: 2

Verdict: ACCEPTED

input
100 200 556919818
42565191 220463466
168162104 512963421
261175087 448523983
469333493 309154626
...

correct output
3

user output
3

Test 29

Group: 2

Verdict: ACCEPTED

input
100 200 366277636
366277636 361714512
174254695 259909254
141132652 161633554
279889879 285691289
...

correct output
3

user output
3

Test 30

Group: 2

Verdict: ACCEPTED

input
100 107 490226028
490226028 423041258
490226028 46334130
490226028 216509848
490226028 134083458
...

correct output
4

user output
4

Test 31

Group: 2

Verdict:

input
100 200 1000000000
541838978 194892766
322660899 610698789
198948481 76594290
331286368 209803771
...

correct output
5

user output
4

Test 32

Group: 2

Verdict: ACCEPTED

input
100 148 454439237
173198908 304790519
78243916 149026456
219470288 371020022
88232561 349895916
...

correct output
1

user output
1

Test 33

Group: 2

Verdict: ACCEPTED

input
100 159 1000000000
846900548 612650612
859815742 61742068
883917005 996178253
113438149 975457133
...

correct output
2

user output
2

Test 34

Group: 2

Verdict: ACCEPTED

input
100 200 1000000000
1000000000 690684452
1000000000 452428454
1000000000 649924239
0 411930549
...

correct output
7

user output
7

Test 35

Group: 2

Verdict:

input
100 198 1000000000
1000000000 729095786
890141101 594401860
591196041 525485574
0 83891349
...

correct output
7

user output
5

Test 36

Group: 2

Verdict: ACCEPTED

input
100 200 1000000000
1000000000 720393927
824126036 829423767
1000000000 205048650
899580021 661286553
...

correct output
2

user output
2

Test 37

Group: 2

Verdict: ACCEPTED

input
100 135 436989274
0 273733425
381884900 83089918
154612631 433160809
436989274 392075286
...

correct output
3

user output
3

Test 38

Group: 2

Verdict: ACCEPTED

input
100 200 1000000000
284762617 953976897
0 90850442
1000000000 742422066
1000000000 872153908
...

correct output
7

user output
7

Test 39

Group: 2

Verdict:

input
100 200 488749297
402051351 343344473
116432108 117781197
146442369 84868582
85614681 28996354
...

correct output
5

user output
4

Test 40

Group: 2

Verdict: ACCEPTED

input
100 184 1000000000
0 759912933
0 130793716
1000000000 733802420
0 727784371
...

correct output
13

user output
13

Test 41

Group: 2

Verdict: ACCEPTED

input
100 157 288148097
0 3788330
25757747 68586962
288148097 161969843
0 45285056
...

correct output
5

user output
5

Test 42

Group: 2

Verdict: ACCEPTED

input
100 145 1000000000
0 735993194
198688336 318480954
0 327794348
0 308307296
...

correct output
2

user output
2

Test 43

Group: 2

Verdict: ACCEPTED

input
100 99 99
0 0
1 0
2 0
3 0
...

correct output
1

user output
1

Test 44

Group: 2

Verdict: ACCEPTED

input
100 99 1
0 0
1 1
0 2
1 3
...

correct output
50

user output
50

Test 45

Group: 3

Verdict:

input
100000 191746 1000000000
467109277 87373752
188927984 477387407
310966969 944969403
116779559 338813117
...

correct output
99

user output
53

Test 46

Group: 3

Verdict: ACCEPTED

input
100000 200000 1000000000
377589717 921951479
902238786 355640577
964396131 236560167
988121622 711074555
...

correct output
10

user output
10

Test 47

Group: 3

Verdict: ACCEPTED

input
100000 200000 1000000000
76693700 40551417
545261842 453952089
7191077 676776171
323601357 878496211
...

correct output
5

user output
5

Test 48

Group: 3

Verdict: ACCEPTED

input
100000 200000 791105502
64540503 517813136
159948458 602276288
315575969 43300913
165868933 345687911
...

correct output
21

user output
21

Test 49

Group: 3

Verdict: ACCEPTED

input
100000 200000 224507347
213939925 172134854
186524558 167276590
195598909 57642717
192342505 160428462
...

correct output
7

user output
7

Test 50

Group: 3

Verdict:

input
100000 160707 1000000000
206630865 501349714
0 364688781
48163386 908163647
21209876 652764209
...

correct output
59

user output
45

Test 51

Group: 3

Verdict:

input
100000 200000 788198261
707723559 298553559
692844178 728362230
296184519 32479811
568980865 186674224
...

correct output
104

user output
49

Test 52

Group: 3

Verdict:

input
100000 200000 752871972
0 426001042
423542589 543419917
276855209 315388539
391126666 28517839
...

correct output
28

user output
22

Test 53

Group: 3

Verdict:

input
100000 200000 250760641
183929371 121596061
35717742 216960428
228413585 240841060
37316534 109894417
...

correct output
103

user output
54

Test 54

Group: 3

Verdict: ACCEPTED

input
100000 200000 344001599
64891064 292979162
161277619 78047732
165186362 88054606
62326979 141981966
...

correct output
1

user output
1

Test 55

Group: 3

Verdict:

input
100000 200000 690814889
556311005 165987588
564229150 385189361
112979022 36140795
432199518 108527807
...

correct output
135

user output
98

Test 56

Group: 3

Verdict: ACCEPTED

input
100000 200000 260601076
98432004 230023345
144961803 126477235
26429506 112311164
14005425 157238962
...

correct output
6

user output
6

Test 57

Group: 3

Verdict: ACCEPTED

input
100000 200000 693386331
583492965 101334721
464385067 141036591
550858292 457351174
630755801 442020496
...

correct output
30

user output
30

Test 58

Group: 3

Verdict:

input
100000 150584 834179490
829309462 560083463
212333734 820244634
618534780 135750156
230209440 69995047
...

correct output
77

user output
57

Test 59

Group: 3

Verdict: ACCEPTED

input
100000 200000 516151236
497333512 338816809
316424486 131364518
270868162 360996820
279307347 272895484
...

correct output
62

user output
62

Test 60

Group: 3

Verdict:

input
100000 200000 937511468
760932523 482418241
0 590702362
0 767847073
0 335383054
...

correct output
117

user output
93

Test 61

Group: 3

Verdict: ACCEPTED

input
100000 200000 1000000000
863663335 38505310
141482998 334402070
805733419 177346396
698360206 120402446
...

correct output
1

user output
1

Test 62

Group: 3

Verdict: ACCEPTED

input
100000 130043 824512124
824512124 497634675
824512124 729393516
824512124 135423271
824512124 217274368
...

correct output
10

user output
10

Test 63

Group: 3

Verdict:

input
100000 200000 150838821
72973123 26352643
79163133 122774062
104179450 141740411
11343152 3373297
...

correct output
135

user output
101

Test 64

Group: 3

Verdict:

input
100000 182142 498824844
427087466 14246667
288245948 209499171
93114396 92993669
216639842 216915412
...

correct output
92

user output
81

Test 65

Group: 3

Verdict: ACCEPTED

input
100000 99999 99999
0 0
1 0
2 0
3 0
...

correct output
1

user output
1

Test 66

Group: 3

Verdict: ACCEPTED

input
100000 99999 1
0 0
1 1
0 2
1 3
...

correct output
50000

user output
50000