CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Hämähäkit
Sender:
Submission time:2015-12-20 16:08:31 +0200
Language:C++
Status:READY
Result:20
Feedback
groupverdictscore
#1ACCEPTED20
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.05 s1details
#6ACCEPTED0.05 s1details
#7ACCEPTED0.05 s1details
#8ACCEPTED0.05 s1details
#9ACCEPTED0.06 s1details
#10ACCEPTED0.05 s1details
#11ACCEPTED0.06 s1details
#12ACCEPTED0.06 s1details
#13ACCEPTED0.04 s1details
#14ACCEPTED0.06 s1details
#15ACCEPTED0.06 s1details
#16ACCEPTED0.05 s1details
#17ACCEPTED0.05 s1details
#18ACCEPTED0.06 s1details
#19ACCEPTED0.05 s1details
#20ACCEPTED0.05 s1details
#21ACCEPTED0.06 s1details
#22ACCEPTED0.05 s1details
#230.05 s2details
#240.06 s2details
#25ACCEPTED0.05 s2details
#260.05 s2details
#27ACCEPTED0.05 s2details
#280.05 s2details
#29ACCEPTED0.05 s2details
#30ACCEPTED0.05 s2details
#310.06 s2details
#32ACCEPTED0.05 s2details
#33ACCEPTED0.05 s2details
#340.05 s2details
#350.05 s2details
#36ACCEPTED0.05 s2details
#370.04 s2details
#38ACCEPTED0.06 s2details
#39ACCEPTED0.06 s2details
#40ACCEPTED0.06 s2details
#41ACCEPTED0.05 s2details
#42ACCEPTED0.05 s2details
#43ACCEPTED0.05 s2details
#44ACCEPTED0.06 s2details
#450.30 s3details
#46ACCEPTED0.28 s3details
#470.21 s3details
#480.20 s3details
#490.21 s3details
#500.74 s3details
#510.28 s3details
#52--3details
#530.28 s3details
#54ACCEPTED0.23 s3details
#550.51 s3details
#56ACCEPTED0.18 s3details
#570.21 s3details
#580.19 s3details
#590.21 s3details
#60--3details
#61ACCEPTED0.20 s3details
#62ACCEPTED0.12 s3details
#630.57 s3details
#640.20 s3details
#65ACCEPTED0.10 s3details
#66--3details

Code

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;

#define F first
#define S second

using namespace std;

vector<pair<ld,ll>> gr[101010];
pair<ll,ll> loc[101010];
int used[101010];
int used2[101010];
int w;
int par[101010];

int dfs(int x) {
  for (int i=0;i<101010;i++) used[i]=0;
  priority_queue<pair<ld,int>> pq;
  pq.push({0,x});
  vector<int> vis;
  while (!pq.empty()) {
    auto y=pq.top();
    pq.pop();
    if (used[y.S] || used2[y.S]) continue;
    used[y.S]=1;
    vis.push_back(y.S);
    if (loc[y.S].F==w) {
      int hlp=y.S;
      while (hlp!=x) {
	used2[hlp]=1;
	hlp=par[hlp];
      }
      used2[x]=1;
      return 1;
    }
    for (auto z : gr[y.S]) {
      if (!used[z.S]) {
	pq.push({z.F,z.S});
	par[z.S]=y.S;
      }
    }
  }
  for (auto r : vis) used2[r]=1;
  return 0;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n,m;
  cin>>n>>m>>w;
  vector<pair<int,int>> beg;
  for (int i=1;i<=n;i++) {
    int x,y;
    cin>>x>>y;
    loc[i]={x,y};
    if (x==0) beg.push_back({-y,i});
  }
  sort(beg.begin(),beg.end());
  for (int i=0;i<m;i++) {
    int a,b;
    cin>>a>>b;
    ld hlp=sqrt((loc[a].F-loc[b].F)*(loc[a].F-loc[b].F)+(loc[a].S-loc[b].S)*(loc[a].S-loc[b].S));
    gr[a].push_back({(loc[b].S-loc[a].S)/hlp,b});
    gr[b].push_back({(loc[a].S-loc[b].S)/hlp,a});
  }
  int res=0;
  for (auto x : beg) {
    res+=dfs(x.S);
  }
  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: 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:

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

correct output
5

user output
4

Test 24

Group: 2

Verdict:

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

correct output
5

user output
4

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
3

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:

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

correct output
3

user output
1

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:

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

correct output
7

user output
5

Test 35

Group: 2

Verdict:

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

correct output
7

user output
4

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

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

correct output
99

user output
11

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:

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

correct output
5

user output
4

Test 48

Group: 3

Verdict:

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

correct output
21

user output
11

Test 49

Group: 3

Verdict:

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

correct output
7

user output
6

Test 50

Group: 3

Verdict:

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

correct output
59

user output
11

Test 51

Group: 3

Verdict:

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

correct output
104

user output
13

Test 52

Group: 3

Verdict:

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

correct output
28

user output
(empty)

Test 53

Group: 3

Verdict:

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

correct output
103

user output
10

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
24

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:

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

correct output
30

user output
16

Test 58

Group: 3

Verdict:

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

correct output
77

user output
14

Test 59

Group: 3

Verdict:

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

correct output
62

user output
24

Test 60

Group: 3

Verdict:

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

correct output
117

user output
(empty)

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
27

Test 64

Group: 3

Verdict:

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

correct output
92

user output
16

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:

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

correct output
50000

user output
(empty)