CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Hämähäkit
Sender:
Submission time:2015-12-20 17:11:34 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED20
#2ACCEPTED30
#3ACCEPTED50
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.05 s1details
#7ACCEPTED0.06 s1details
#8ACCEPTED0.06 s1details
#9ACCEPTED0.06 s1details
#10ACCEPTED0.05 s1details
#11ACCEPTED0.05 s1details
#12ACCEPTED0.06 s1details
#13ACCEPTED0.05 s1details
#14ACCEPTED0.06 s1details
#15ACCEPTED0.05 s1details
#16ACCEPTED0.05 s1details
#17ACCEPTED0.06 s1details
#18ACCEPTED0.05 s1details
#19ACCEPTED0.05 s1details
#20ACCEPTED0.05 s1details
#21ACCEPTED0.05 s1details
#22ACCEPTED0.06 s1details
#23ACCEPTED0.05 s2details
#24ACCEPTED0.05 s2details
#25ACCEPTED0.05 s2details
#26ACCEPTED0.05 s2details
#27ACCEPTED0.05 s2details
#28ACCEPTED0.05 s2details
#29ACCEPTED0.06 s2details
#30ACCEPTED0.06 s2details
#31ACCEPTED0.05 s2details
#32ACCEPTED0.06 s2details
#33ACCEPTED0.06 s2details
#34ACCEPTED0.05 s2details
#35ACCEPTED0.06 s2details
#36ACCEPTED0.06 s2details
#37ACCEPTED0.05 s2details
#38ACCEPTED0.05 s2details
#39ACCEPTED0.06 s2details
#40ACCEPTED0.06 s2details
#41ACCEPTED0.05 s2details
#42ACCEPTED0.06 s2details
#43ACCEPTED0.05 s2details
#44ACCEPTED0.06 s2details
#45ACCEPTED0.37 s3details
#46ACCEPTED0.36 s3details
#47ACCEPTED0.31 s3details
#48ACCEPTED0.33 s3details
#49ACCEPTED0.30 s3details
#50ACCEPTED0.32 s3details
#51ACCEPTED0.38 s3details
#52ACCEPTED0.36 s3details
#53ACCEPTED0.37 s3details
#54ACCEPTED0.37 s3details
#55ACCEPTED0.36 s3details
#56ACCEPTED0.30 s3details
#57ACCEPTED0.37 s3details
#58ACCEPTED0.30 s3details
#59ACCEPTED0.34 s3details
#60ACCEPTED0.34 s3details
#61ACCEPTED0.31 s3details
#62ACCEPTED0.25 s3details
#63ACCEPTED0.35 s3details
#64ACCEPTED0.32 s3details
#65ACCEPTED0.19 s3details
#66ACCEPTED0.18 s3details

Compiler report

input/code.cpp: In function 'bool go(int, int)':
input/code.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<tie[c].size(); ++i){
                    ^
input/code.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<tie[c].size(); ++i){
                  ^
input/code.cpp: In function 'int main()':
input/code.cpp:90:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<tie[0].size(); ++i){
                  ^

Code

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

int n, m, w;

vector<pair<int, int> > nd;

vector<int> tie[101010];
long double angle[101010];

bool unav[101010];


#define PI 3.14159265358979l
long double ad;
long double ang(int x, int y){
  long double a=atan2(x, y)+ad;
  if (a<0) a+=2*PI;
  if (a>2*PI) a-=2*PI;
  return a;
}


bool fsrt(int a, int b){
  return angle[a]<angle[b];
}

int n0;
bool go(int c, int p){
  if (unav[c]) return 0;
  unav[c]=1;
  if (nd[c].F==w) return 1;
  
  if (c && tie[c].size()>1){
    int dx=nd[p].F-nd[c].F;
    int dy=nd[p].S-nd[c].S;
    ad=0;
    long double a=ang(dx, dy);
    ad=2.0*PI-a;
    
    for (int i=0; i<tie[c].size(); ++i){
      int a=tie[c][i];
      angle[a]=ang(nd[a].F-nd[c].F, nd[a].S-nd[c].S);
    }
    sort(tie[c].begin(), tie[c].end(), fsrt);
  }
  for (int i=0; i<tie[c].size(); ++i){
    if (c==0){
      if (i<n0) i=n0;
      n0=i;
    }
    if (unav[tie[c][i]]) continue;
    if (go(tie[c][i], c)) return 1;
  }
  return 0;
}





int main(){
  cin >> n >> m >> w;
  nd.push_back(make_pair(-1, 0));
  for (int i=1; i<=n; ++i){
    int x, y;
    cin >> x >> y;
    nd.push_back(make_pair(x, y));
  }
  
  for (int i=0; i<m; ++i){
    int a, b;
    cin >> a >> b;
    tie[a].push_back(b);
    tie[b].push_back(a);
  }
  for (int i=1; i<=n; ++i){
    if (nd[i].F==0){
      tie[0].push_back(i);
      tie[i].push_back(0);
    }
  }
  
  ad=0;
  for (int i=0; i<tie[0].size(); ++i){
    int a=tie[0][i];
    angle[a]=ang(nd[a].F-nd[0].F, nd[a].S-nd[0].S);    
  }
  sort(tie[0].begin(), tie[0].end(), fsrt);

  int ans=0;
  while (go(0, 0)){
    unav[0]=0;
    ++ans; 
  }
  cout << ans << endl;
}

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: ACCEPTED

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

correct output
5

user output
5

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: ACCEPTED

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

correct output
7

user output
7

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: ACCEPTED

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

correct output
5

user output
5

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: ACCEPTED

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

correct output
99

user output
99

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: ACCEPTED

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

correct output
59

user output
59

Test 51

Group: 3

Verdict: ACCEPTED

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

correct output
104

user output
104

Test 52

Group: 3

Verdict: ACCEPTED

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

correct output
28

user output
28

Test 53

Group: 3

Verdict: ACCEPTED

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

correct output
103

user output
103

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: ACCEPTED

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

correct output
135

user output
135

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: ACCEPTED

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

correct output
77

user output
77

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: ACCEPTED

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

correct output
117

user output
117

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: ACCEPTED

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

correct output
135

user output
135

Test 64

Group: 3

Verdict: ACCEPTED

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

correct output
92

user output
92

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