CSES - APIO 2016 - Results
Submission details
Task:Fireworks
Sender:ArktinenKarpalo
Submission time:2019-04-14 01:49:24 +0300
Language:C++
Status:READY
Result:26
Feedback
groupverdictscore
#1ACCEPTED7
#2ACCEPTED19
#30
#40
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2, 3, 4details
#2ACCEPTED0.02 s1, 2, 3, 4details
#3ACCEPTED0.03 s1, 2, 3, 4details
#4ACCEPTED0.02 s1, 2, 3, 4details
#5ACCEPTED0.03 s1, 2, 3, 4details
#6ACCEPTED0.02 s1, 2, 3, 4details
#7ACCEPTED0.02 s1, 2, 3, 4details
#8ACCEPTED0.02 s1, 2, 3, 4details
#9ACCEPTED0.03 s1, 2, 3, 4details
#10ACCEPTED0.03 s1, 2, 3, 4details
#11ACCEPTED0.02 s2, 3, 4details
#12ACCEPTED0.03 s2, 3, 4details
#13ACCEPTED0.04 s2, 3, 4details
#14ACCEPTED0.05 s2, 3, 4details
#15ACCEPTED0.04 s2, 3, 4details
#16ACCEPTED0.04 s2, 3, 4details
#17ACCEPTED0.04 s2, 3, 4details
#18ACCEPTED0.04 s2, 3, 4details
#19ACCEPTED0.05 s2, 3, 4details
#20ACCEPTED0.05 s2, 3, 4details
#21ACCEPTED0.05 s2, 3, 4details
#22ACCEPTED0.04 s2, 3, 4details
#23ACCEPTED0.05 s2, 3, 4details
#24ACCEPTED0.05 s2, 3, 4details
#25ACCEPTED0.07 s2, 3, 4details
#26ACCEPTED0.06 s2, 3, 4details
#27ACCEPTED0.05 s2, 3, 4details
#28ACCEPTED0.06 s2, 3, 4details
#29ACCEPTED0.05 s2, 3, 4details
#30ACCEPTED0.06 s2, 3, 4details
#310.07 s3, 4details
#320.15 s3, 4details
#330.20 s3, 4details
#340.27 s3, 4details
#350.02 s3, 4details
#360.01 s3, 4details
#370.02 s3, 4details
#380.02 s3, 4details
#390.03 s3, 4details
#400.02 s3, 4details
#410.03 s3, 4details
#420.02 s3, 4details
#430.03 s3, 4details
#440.03 s3, 4details
#450.03 s3, 4details
#460.02 s3, 4details
#470.03 s3, 4details
#480.02 s3, 4details
#490.03 s3, 4details
#500.03 s3, 4details
#510.03 s3, 4details
#520.03 s3, 4details
#530.03 s3, 4details
#540.02 s3, 4details
#55ACCEPTED0.02 s3, 4details
#560.04 s4details
#570.05 s4details
#580.06 s4details
#590.08 s4details
#600.09 s4details
#610.12 s4details
#620.13 s4details
#630.14 s4details
#640.16 s4details
#650.16 s4details
#660.13 s4details
#670.14 s4details
#680.14 s4details
#690.13 s4details
#700.15 s4details
#710.15 s4details
#720.12 s4details
#730.12 s4details
#740.13 s4details
#750.12 s4details
#760.12 s4details
#770.12 s4details
#780.12 s4details
#790.12 s4details
#80ACCEPTED0.11 s4details

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define M 1000000007
#define N (1<<18)
#define P complex<long long>
#define X real()
#define Y imag()

using namespace std;

int n, m, p[303030], c[303030], d[303][303], z[303030];
vector<int> v;
vector<int> vrk[303030];

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	if(n == 1) {
		for(int i=0; i<m; i++) {
			cin >> p[i] >> c[i];
			v.push_back(c[i]);
		}
		sort(v.begin(), v.end());
		ll ans = 0;
		for(auto u:v) {
			ans += abs(u-v[v.size()/2]);
		}
		cout << ans;
	} else {
		for(int i=2; i<=m+n; i++) {
			cin >> p[i] >> c[i];
			vrk[i].push_back(p[i]);
			vrk[p[i]].push_back(i);
		}
		stack<int> stk;
		queue<int> q;
		q.push(1);
		while(!q.empty()) {
			int s = q.front();
			q.pop();
			if(z[s])
				continue;
			stk.push(s);
			z[s] = 1;
			for(auto u:vrk[s]) {
				if(z[u])
					continue;
				q.push(u);
			}
		}
		while(!stk.empty()) {
			int s = stk.top();
			stk.pop();
			for(int i=0; i<=300; i++) {
				if(vrk[s].size() == 1 && s > 1) {
					d[s][i] = abs(c[s]-i);
					continue;
				}
				d[s][i] = 1e9;
				for(int j=0; j<=i; j++) {
					int luku = abs(c[s]-j);
					for(auto u:vrk[s]) {
						if(u == p[s])
							continue;
						luku += d[u][i-j];
					}
					d[s][i] = min(d[s][i], luku);
				}
			}
		}
		int ans = 1e9;
		for(int i=0; i<=300; i++)
			ans = min(ans, d[1][i]);
		cout << ans;
	}
}

Test details

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
1 1
1 594911537

correct output
0

user output
0

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
1 9
1 825879648
1 544663269
1 523587648
1 265820061
...

correct output
1860127768

user output
1860127768

Test 3

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
1 91
1 385900550
1 26102977
1 667546315
1 172015997
...

correct output
22110262696

user output
22110262696

Test 4

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
1 89
1 82978004
1 725546925
1 824854855
1 134535238
...

correct output
22880340918

user output
22880340918

Test 5

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
1 84
1 887742276
1 580594619
1 950555150
1 771426100
...

correct output
17356166508

user output
17356166508

Test 6

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
1 91
1 162454772
1 470082830
1 143610614
1 831070014
...

correct output
22730104544

user output
22730104544

Test 7

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
1 98
1 492984845
1 603301504
1 827779013
1 543424271
...

correct output
22934390057

user output
22934390057

Test 8

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
1 96
1 676422399
1 383144101
1 908806402
1 195899706
...

correct output
22860762666

user output
22860762666

Test 9

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
1 87
1 411199713
1 407170309
1 411199713
1 690858790
...

correct output
15512296902

user output
15512296902

Test 10

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
1 95
1 556207110
1 813583629
1 263051757
1 263051757
...

correct output
18060215274

user output
18060215274

Test 11

Group: 2, 3, 4

Verdict: ACCEPTED

input
6 7
1 65
1 115
2 33
1 298
...

correct output
302

user output
302

Test 12

Group: 2, 3, 4

Verdict: ACCEPTED

input
13 23
1 48
2 167
1 248
2 48
...

correct output
374

user output
374

Test 13

Group: 2, 3, 4

Verdict: ACCEPTED

input
21 38
1 24
1 32
2 177
3 203
...

correct output
1917

user output
1917

Test 14

Group: 2, 3, 4

Verdict: ACCEPTED

input
33 38
1 18
1 81
2 100
1 245
...

correct output
804

user output
804

Test 15

Group: 2, 3, 4

Verdict: ACCEPTED

input
93 1
1 2
2 2
3 1
4 1
...

correct output
0

user output
0

Test 16

Group: 2, 3, 4

Verdict: ACCEPTED

input
55 62
1 118
2 144
1 264
1 113
...

correct output
1219

user output
1219

Test 17

Group: 2, 3, 4

Verdict: ACCEPTED

input
63 67
1 121
2 106
1 147
3 4
...

correct output
934

user output
934

Test 18

Group: 2, 3, 4

Verdict: ACCEPTED

input
66 88
1 246
2 6
3 2
4 21
...

correct output
594

user output
594

Test 19

Group: 2, 3, 4

Verdict: ACCEPTED

input
78 99
1 204
1 105
1 137
2 3
...

correct output
1443

user output
1443

Test 20

Group: 2, 3, 4

Verdict: ACCEPTED

input
89 101
1 120
2 60
1 229
1 156
...

correct output
1341

user output
1341

Test 21

Group: 2, 3, 4

Verdict: ACCEPTED

input
101 112
1 172
2 49
3 19
4 3
...

correct output
939

user output
939

Test 22

Group: 2, 3, 4

Verdict: ACCEPTED

input
109 126
1 111
2 115
3 33
1 55
...

correct output
1725

user output
1725

Test 23

Group: 2, 3, 4

Verdict: ACCEPTED

input
117 141
1 107
1 44
2 46
3 99
...

correct output
1931

user output
1931

Test 24

Group: 2, 3, 4

Verdict: ACCEPTED

input
134 137
1 232
2 11
1 91
1 60
...

correct output
1934

user output
1934

Test 25

Group: 2, 3, 4

Verdict: ACCEPTED

input
293 1
1 1
2 1
3 1
4 1
...

correct output
0

user output
0

Test 26

Group: 2, 3, 4

Verdict: ACCEPTED

input
139 161
1 108
2 10
2 10
3 51
...

correct output
2627

user output
2627

Test 27

Group: 2, 3, 4

Verdict: ACCEPTED

input
130 170
1 166
2 66
1 9
1 94
...

correct output
1683

user output
1683

Test 28

Group: 2, 3, 4

Verdict: ACCEPTED

input
137 163
1 14
2 97
3 91
1 91
...

correct output
1711

user output
1711

Test 29

Group: 2, 3, 4

Verdict: ACCEPTED

input
140 160
1 116
2 62
1 228
3 54
...

correct output
2102

user output
2102

Test 30

Group: 2, 3, 4

Verdict: ACCEPTED

input
121 179
1 16
1 66
2 7
3 69
...

correct output
2300

user output
2300

Test 31

Group: 3, 4

Verdict:

input
301 162
1 920419098
2 13883963
3 922640814
4 576832601
...

correct output
132811066618

user output
873834413

Test 32

Group: 3, 4

Verdict:

input
717 419
1 376688158
2 38218218
3 741729439
4 690180775
...

correct output
346801924243

user output
-1194457340

Test 33

Group: 3, 4

Verdict:

input
1039 570
1 763342664
2 630794
3 305459828
4 879255848
...

correct output
507266242467

user output
1000000000

Test 34

Group: 3, 4

Verdict:

input
1426 825
1 21845067
2 830363113
3 417705301
4 289927464
...

correct output
697458913436

user output
1000000000

Test 35

Group: 3, 4

Verdict:

input
1870 1054
1 398066557
2 678052759
3 670475186
4 861116608
...

correct output
905295828241

user output
(empty)

Test 36

Group: 3, 4

Verdict:

input
2275 1322
1 418164933
2 775647573
3 736430086
4 987537454
...

correct output
1095328057433

user output
(empty)

Test 37

Group: 3, 4

Verdict:

input
2587 1483
1 499164205
2 221727844
3 930497471
4 520918543
...

correct output
1297800304292

user output
(empty)

Test 38

Group: 3, 4

Verdict:

input
2987 1757
1 82381521
2 474824518
3 920067780
4 425601747
...

correct output
1488454586050

user output
(empty)

Test 39

Group: 3, 4

Verdict:

input
3123 1877
1 831706841
2 781051540
3 70423592
4 648655398
...

correct output
1541144647994

user output
(empty)

Test 40

Group: 3, 4

Verdict:

input
3151 1849
1 324493214
2 131808411
3 293261515
4 355022995
...

correct output
1541693936031

user output
(empty)

Test 41

Group: 3, 4

Verdict:

input
4999 1
1 999993036
2 999994800
3 999993285
4 999997650
...

correct output
0

user output
(empty)

Test 42

Group: 3, 4

Verdict:

input
4998 2
1 999998194
2 999996844
3 999993710
4 999992665
...

correct output
4997974986577

user output
(empty)

Test 43

Group: 3, 4

Verdict:

input
4900 100
1 999991561
2 999991023
1 999999431
3 999996825
...

correct output
2450987727801

user output
(empty)

Test 44

Group: 3, 4

Verdict:

input
2499 2500
1 439460934
2 783025325
3 559459286
4 10655632
...

correct output
1873824603983

user output
(empty)

Test 45

Group: 3, 4

Verdict:

input
2364 2635
1 800243976
2 560941019
3 611820188
4 110334476
...

correct output
1664606780993

user output
(empty)

Test 46

Group: 3, 4

Verdict:

input
2396 2603
1 143164022
2 651107986
3 793461024
4 519935252
...

correct output
1661418840499

user output
(empty)

Test 47

Group: 3, 4

Verdict:

input
53 4943
1 108701533
1 762016066
2 158864139
2 229999782
...

correct output
1247558162340

user output
(empty)

Test 48

Group: 3, 4

Verdict:

input
48 4911
1 614868110
2 916120791
2 285591885
2 743652924
...

correct output
1234131077649

user output
(empty)

Test 49

Group: 3, 4

Verdict:

input
5 4504
1 890856182
1 78084000
1 16801616
1 466720154
...

correct output
1102143195362

user output
(empty)

Test 50

Group: 3, 4

Verdict:

input
6 4994
1 456281990
1 365849799
1 791098247
1 586851273
...

correct output
1233299707784

user output
(empty)

Test 51

Group: 3, 4

Verdict:

input
2 4275
1 170424242
2 157296367
2 45154595
2 278995331
...

correct output
1063932478026

user output
(empty)

Test 52

Group: 3, 4

Verdict:

input
2 4163
1 790277286
2 763894393
2 322193685
2 724891720
...

correct output
1034079385209

user output
(empty)

Test 53

Group: 3, 4

Verdict:

input
110 4388
1 129329989
2 290770655
3 399085375
4 480394263
...

correct output
1127480276183

user output
(empty)

Test 54

Group: 3, 4

Verdict:

input
133 4533
1 981373360
2 950241053
2 691321246
2 34700278
...

correct output
1141003981040

user output
(empty)

Test 55

Group: 3, 4

Verdict: ACCEPTED

input
1 4999
1 295391035
1 196472221
1 340660725
1 715185782
...

correct output
1243420232820

user output
1243420232820

Test 56

Group: 4

Verdict:

input
8275 4844
1 107176958
2 220278740
3 824198376
4 659292090
...

correct output
4075544302733

user output
(empty)

Test 57

Group: 4

Verdict:

input
31089 18103
1 220776148
2 692381056
3 346957199
4 713647714
...

correct output
15494390766791

user output
(empty)

Test 58

Group: 4

Verdict:

input
53299 30967
1 855240498
2 154546935
3 234034227
4 308783540
...

correct output
26365637274114

user output
(empty)

Test 59

Group: 4

Verdict:

input
67684 39423
1 255518383
2 383661588
3 4810446
4 525628041
...

correct output
33302307710368

user output
(empty)

Test 60

Group: 4

Verdict:

input
90485 52695
1 805472417
2 142689110
3 189995996
4 810067756
...

correct output
44808404427421

user output
(empty)

Test 61

Group: 4

Verdict:

input
112735 65518
1 770253575
2 702318170
3 60500435
4 804626739
...

correct output
55559390823214

user output
(empty)

Test 62

Group: 4

Verdict:

input
128111 74216
1 594119529
2 260263871
3 829129790
4 61304166
...

correct output
63232674003693

user output
(empty)

Test 63

Group: 4

Verdict:

input
141176 82297
1 693896082
2 79828028
3 185755259
4 302343462
...

correct output
69570597946144

user output
(empty)

Test 64

Group: 4

Verdict:

input
168797 97750
1 953762145
2 799653575
3 1693874
4 481530444
...

correct output
83148807654414

user output
(empty)

Test 65

Group: 4

Verdict:

input
178123 103497
1 799897547
2 350049341
3 602276190
4 239135262
...

correct output
87922013507367

user output
(empty)

Test 66

Group: 4

Verdict:

input
299999 1
1 999997465
2 999994753
3 999993664
4 999996715
...

correct output
0

user output
(empty)

Test 67

Group: 4

Verdict:

input
299998 2
1 999993391
2 999996797
3 999991089
4 999993962
...

correct output
299996497393509

user output
(empty)

Test 68

Group: 4

Verdict:

input
299225 775
1 999998776
2 999997156
1 999995160
3 999995715
...

correct output
150081246669606

user output
(empty)

Test 69

Group: 4

Verdict:

input
149999 150000
1 554189173
2 861829121
3 829225860
4 213727479
...

correct output
111986891597599

user output
(empty)

Test 70

Group: 4

Verdict:

input
147647 152352
1 628094974
2 266020444
3 538104237
4 313406555
...

correct output
106170824468065

user output
(empty)

Test 71

Group: 4

Verdict:

input
147747 152252
1 913818026
2 961911782
3 181336455
4 413853399
...

correct output
106256085275254

user output
(empty)

Test 72

Group: 4

Verdict:

input
2982 297006
1 930075003
1 590093806
1 117783415
1 856438532
...

correct output
73845050003347

user output
(empty)

Test 73

Group: 4

Verdict:

input
3003 296965
1 205758931
1 101020775
1 713047771
1 241600845
...

correct output
74124179113620

user output
(empty)

Test 74

Group: 4

Verdict:

input
556 299213
1 822254263
1 461344563
1 969727098
1 2496619
...

correct output
74536361263414

user output
(empty)

Test 75

Group: 4

Verdict:

input
547 299336
1 275207239
2 158520026
2 78057664
2 471627439
...

correct output
74670326835464

user output
(empty)

Test 76

Group: 4

Verdict:

input
148 297658
1 249902206
1 621047085
1 329925101
1 425583316
...

correct output
74066800366955

user output
(empty)

Test 77

Group: 4

Verdict:

input
153 298512
1 287723200
1 471371331
1 378527194
1 664526236
...

correct output
74331631754273

user output
(empty)

Test 78

Group: 4

Verdict:

input
2066 290658
1 615414698
2 862401797
3 543802391
4 120919462
...

correct output
72818357741108

user output
(empty)

Test 79

Group: 4

Verdict:

input
780 292489
1 997556321
2 910768044
2 663206818
2 848566643
...

correct output
73036155725083

user output
(empty)

Test 80

Group: 4

Verdict: ACCEPTED

input
1 299999
1 607350158
1 653685957
1 456250530
1 316455876
...

correct output
74718409994641

user output
74718409994641