CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Hämähäkit
Sender:Henrik Lievonen
Submission time:2015-12-20 15:49:04 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1details
#2ACCEPTED0.05 s1details
#30.05 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.06 s1details
#7ACCEPTED0.05 s1details
#80.05 s1details
#9ACCEPTED0.06 s1details
#10ACCEPTED0.05 s1details
#11ACCEPTED0.04 s1details
#12ACCEPTED0.06 s1details
#13ACCEPTED0.05 s1details
#14ACCEPTED0.06 s1details
#15ACCEPTED0.04 s1details
#16ACCEPTED0.06 s1details
#17ACCEPTED0.05 s1details
#18ACCEPTED0.05 s1details
#19ACCEPTED0.05 s1details
#20ACCEPTED0.06 s1details
#21ACCEPTED0.06 s1details
#22ACCEPTED0.06 s1details
#230.05 s2details
#240.05 s2details
#25ACCEPTED0.06 s2details
#260.06 s2details
#270.04 s2details
#280.06 s2details
#290.06 s2details
#300.06 s2details
#310.05 s2details
#32ACCEPTED0.05 s2details
#330.06 s2details
#340.05 s2details
#350.06 s2details
#36ACCEPTED0.06 s2details
#370.05 s2details
#380.05 s2details
#390.06 s2details
#400.05 s2details
#41ACCEPTED0.05 s2details
#42ACCEPTED0.06 s2details
#43ACCEPTED0.05 s2details
#44ACCEPTED0.06 s2details
#450.32 s3details
#460.33 s3details
#470.32 s3details
#480.37 s3details
#490.31 s3details
#500.29 s3details
#510.31 s3details
#520.33 s3details
#530.32 s3details
#54ACCEPTED0.34 s3details
#550.32 s3details
#560.32 s3details
#570.32 s3details
#580.28 s3details
#590.32 s3details
#600.32 s3details
#61ACCEPTED0.32 s3details
#620.28 s3details
#630.31 s3details
#640.30 s3details
#65ACCEPTED0.17 s3details
#66ACCEPTED0.17 s3details

Code

// E

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> P;

P poss[100100];
bool exists[100100];
vector<int> cons[100100];
int n, m, w;

struct angle_cmp {
  ll x, y;
  angle_cmp(int i) : x(poss[i].first), y(poss[i].second) {}
  angle_cmp(ll x, ll y) : x(x), y(y) {}
  
  static const int quad(const ll x, const ll y) {
    // 0 | 1
    // -----
    // 3 | 2
    if (y < 0) {
      if (x < 0)
	return 0;
      return 1;
    }
    if (x < 0)
      return 3;
    return 2;
  }
  
  bool operator()(const int a, const int b) const {
    ll ax = poss[a].first - x;
    ll ay = poss[a].second - y;
    ll bx = poss[b].first - x;
    ll by = poss[b].second - y;
    
    int aq = quad(ax, ay);
    int bq = quad(bx, by);
    if (aq != bq) return aq < bq;
    
    return ax*by - ay*bx > 0;
  }
};

bool findRoute(int i) {
  if (!exists[i])
    return false;
  exists[i] = 0;
  
  if (poss[i].first == w)
    return true;
  
  for (int con : cons[i]) {
    if (findRoute(con))
      return true;
  }
  return false;
}

int main() {
  cin >> n >> m >> w;
  vector<int> starts;
  for (int i = 1; i <= n; i++) {
    cin >> poss[i].first >> poss[i].second;
    if (poss[i].first == 0)
      starts.push_back(i);
    exists[i] = 1;
  }
  
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    cons[a].push_back(b);
    cons[b].push_back(a);
  }
  
  for (int i = 1; i <= n; i++) {
    sort(cons[i].begin(), cons[i].end(), angle_cmp(i));
  }
  
  int res = 0;
  for (int start : starts) {
    res += findRoute(start);
  }
  
  cout<<res<<'\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:

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

correct output
2

user output
1

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:

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

correct output
3

user output
2

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:

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

correct output
5

user output
3

Test 24

Group: 2

Verdict:

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

correct output
5

user output
3

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:

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

correct output
5

user output
2

Test 27

Group: 2

Verdict:

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

correct output
2

user output
1

Test 28

Group: 2

Verdict:

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

correct output
3

user output
2

Test 29

Group: 2

Verdict:

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

correct output
3

user output
1

Test 30

Group: 2

Verdict:

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

correct output
4

user output
3

Test 31

Group: 2

Verdict:

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

correct output
5

user output
1

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:

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

correct output
2

user output
1

Test 34

Group: 2

Verdict:

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

correct output
7

user output
3

Test 35

Group: 2

Verdict:

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

correct output
7

user output
2

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:

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

correct output
3

user output
2

Test 38

Group: 2

Verdict:

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

correct output
7

user output
4

Test 39

Group: 2

Verdict:

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

correct output
5

user output
2

Test 40

Group: 2

Verdict:

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

correct output
13

user output
12

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
7

Test 46

Group: 3

Verdict:

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

correct output
10

user output
9

Test 47

Group: 3

Verdict:

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

correct output
5

user output
2

Test 48

Group: 3

Verdict:

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

correct output
21

user output
4

Test 49

Group: 3

Verdict:

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

correct output
7

user output
3

Test 50

Group: 3

Verdict:

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

correct output
59

user output
8

Test 51

Group: 3

Verdict:

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

correct output
104

user output
3

Test 52

Group: 3

Verdict:

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

correct output
28

user output
6

Test 53

Group: 3

Verdict:

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

correct output
103

user output
6

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
8

Test 56

Group: 3

Verdict:

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

correct output
6

user output
1

Test 57

Group: 3

Verdict:

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

correct output
30

user output
8

Test 58

Group: 3

Verdict:

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

correct output
77

user output
6

Test 59

Group: 3

Verdict:

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

correct output
62

user output
6

Test 60

Group: 3

Verdict:

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

correct output
117

user output
6

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:

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

correct output
10

user output
3

Test 63

Group: 3

Verdict:

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

correct output
135

user output
6

Test 64

Group: 3

Verdict:

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

correct output
92

user output
4

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