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

Code

#include <iostream>
#include <complex>
#include <vector>
#include <algorithm>
using namespace std;
typedef complex<double> V;

const int MN = 1<<18;
V vs[MN];

vector<int> es[MN];
bool done[MN];
bool isEnd[MN];

bool dfs(int n, int f) {
	done[n]=1;
//	cout<<"dfs "<<f<<" -> "<<n<<'\n';
	if (isEnd[n]) return 1;
	int st=0;
	if (f>=0) {
		while(es[n][st] != f) ++st;
	}
	int s=es[n].size();
	for(int i=0; i<s; ++i) {
		int t=es[n][(st+i)%s];
		if (done[t]) continue;
//		done[e]=done[e^1]=1;
		if (dfs(t, n)) {
			return 1;
		}
	}
//	cout<<"return "<<f<<" <- "<<n<<'\n';
	return 0;
}

V curV;
double ang(int x) {
	V v = vs[x] - curV;
	return -atan2(v.real(), v.imag());
}
bool cmp(int a, int b) {
	return ang(a) < ang(b);
}

bool cmpy(int a, int b) {
	return vs[a].imag() < vs[b].imag();
}

int main() {
	int n,m,w;
	cin>>n>>m>>w;
	vector<int> starts;
	for(int i=0; i<n; ++i) {
		int x,y;
		cin>>x>>y;
		vs[i] = V(x,y);
		isEnd[i] = x==w;
		if (x==0) {
			starts.push_back(i);
		}
	}
	for(int i=0; i<m; ++i) {
		int a,b;
		cin>>a>>b;
		--a,--b;
		es[a].push_back(b);
		es[b].push_back(a);
	}
	for(int i=0; i<n; ++i) {
		curV = vs[i];
		sort(es[i].begin(), es[i].end(), cmp);
//		cout<<i<<' '<<curV<<": ";for(int x: es[i]) cout<<to[x]<<' ';cout<<'\n';
	}

	sort(starts.begin(), starts.end(), cmpy);
	int res=0;
	for(int v: starts) {
//		cout<<"start "<<v<<'\n';
		if (!done[v] && dfs(v, -1)) {
//			cout<<"found\n";
			++res;
		}
	}
	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: 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