h2331GiftCertificateDistribute
unknownplain_text
a month ago
34 kB
11
Indexable
Never
Gift Certificate Distribution
*** Problem
- N groups, for each: several departments are organized into a single tree.
- A department has an ID and the number of people it belongs to, and has a maximum of 3 sub-departments.
- We are going to distribute gift certificates to N groups according to the number of people. The total number of gift certificates is K
*** Distrubute rules
1. If the total number of people is K or less, gift certificates will be distributed according to the number of people in each group.
2. If the total number of people is greater than K, the upper limit of the number L is determined. If the number of people in the groupis less than L, gift certificates will be given according to the number of people in the group, and if the number of people in the group exceeds L, L gift certificates will be given.
*** API
1. int add(int mId, int mNum, int mParent)
Add the mId department as a subdivision of the mParent department.
The number of people in the mId department is mNum. The mParent value is given only the ID of the department that is always present.
If there are already 3 sub-departments in the mParent department, the addition fails and returns -1.
The mId value does not give the ID of a department that already exists.
///Parameters
mId: Department ID ( 1 ≤ mId ≤ 1,000,000,000 )
mNum: Department personnel Number ( 1 ≤ mNum ≤ 100 )
mParent: Parent Department ID ( 1 ≤ mParent ≤ 1,000,000,000 )
///Returns
If the addition is successful, the sum of the headcount of all departments under it, including the mParent department, will be returned.
In other words, the number of people in a subtree where mParent is the root node. Return the sum.
If the addition fails, -1 is returned
2. int remove(int mId)
Delete the department with the ID mId. All departments under the mId department will also be deleted.
If the ID of the top-level department is It is not given.
The ID of the department that has already been deleted is It may be given.
If the mId department does not exist, it returns -1.
///Parameters
mId: Department ID ( 1 ≤ mId ≤ 1,000,000,000 )
///Returns
mId department exists In this case, the sum of the number of personnel of all departments under it, including the mId department, shall be returned. In other words, the sum of the people in the subtree whose mId is the root node is Return.
The mId department does not exist Otherwise, -1 is returned.
3. int distribute(int K)
Divide as many as possible into N groups according to the distribution rules. When given, the largest value of the number of vouchers distributed to each group is returned.
///Parameters
K: Number of Gift Certificates ( N ≤ K ≤ 800,000 )
///Returns
Allocated to each group Returns the largest value of the number of gift certificates
*** testcase
25 100
12
1 3
7 25
4 5
2 40
2 3 5 4 10
2 9 5 7 30
2 1 15 4 25
2 8 10 1 25
4 100 35
2 6 20 4 55
4 109 39
2 5 20 9 25
4 131 45
3 1 25
4 110 40
30
1 3
6932607 76
9283574 79
3799193 94
2 639546083 72 9283574 151
2 7490781 42 3799193 136
2 6568711 8 3799193 144
2 572001 54 7490781 96
2 3518315 8 7490781 104
2 2144677 10 3799193 216
2 2988431 28 9283574 179
2 5269673 6 3518315 14
4 463 208
2 2948033 98 6568711 106
2 973693771 88 2144677 98
4 551 296
2 5289891 12 5269673 18
2 6859805 6 5269673 24
2 4425671 76 973693771 164
2 339118881 86 5269673 110
2 6955307 44 5289891 56
3 973693771 164
4 666 411
2 231882 47 6859805 53
4 647 392
2 9653352 5 572001 59
2 9669600 9 6568711 115
3 5289891 56
2 106931781 50 5269673 195
2 9415005 2 9669600 11
3 6955307 -1
2 441886 51 339118881 137
2 2048342 75 441886 126
50
1 5
842745 82
5076024 77
8500675 48
5835274 11
8640445 62
2 4506471 64 8500675 112
2 7470401 90 5076024 167
2 8674635 60 5835274 71
4 490 163
2 2898467 44 8640445 106
2 2670877 70 7470401 160
2 2987079 36 4506471 100
2 3136289 14 5076024 251
2 4331691 56 2987079 92
2 9033317 50 3136289 64
2 5585359 84 9033317 134
2 7877097 10 4331691 66
2 2307507 68 4331691 134
2 958168877 30 5585359 114
2 9148119 84 9033317 248
2 706908721 6 4331691 140
2 4766523 88 2307507 156
2 3391221 74 5585359 188
2 601626335 100 9033317 422
4 1138 503
2 8648247 76 3391221 150
2 2536849 90 601626335 190
2 2727195 96 4331691 -1
2 5728981 38 601626335 228
2 4452159 72 8674635 132
2 1151321 2 706908721 8
2 7337251 92 2536849 182
4 1460 751
2 5553147 28 3391221 178
2 1452597 78 958168877 108
3 2536849 182
2 7346966 95 9148119 179
2 6891000 61 5553147 89
2 9865290 47 4766523 135
2 407564 17 6891000 78
2 2674110 39 4766523 174
2 5573344 37 5553147 143
2 4820824 61 9865290 108
4 1842 986
3 4452159 72
2 5770171 28 2898467 72
2 3991925 22 6891000 100
2 7363039 8 5835274 79
2 2772089 14 1452597 92
2 7391171 24 8640445 158
2 9064253 78 6891000 178
2 9785703 16 1452597 108
3 6891000 178
4 1672 828
100
1 10
364095 24
9369398 71
9703257 78
7834648 53
8930467 36
2908778 59
1373085 86
7485100 61
6813639 32
9353566 63
2 1317632 49 9353566 112
2 4324882 63 6813639 95
2 8923924 93 4324882 156
2 4541446 95 8923924 188
2 989800 45 9369398 116
2 4681914 27 1317632 76
2 3799292 65 4541446 160
2 7581102 59 6813639 407
4 932 280
2 2561766 67 1317632 143
2 1206856 69 1317632 212
4 980 233
2 6181056 97 1206856 166
2 2477394 91 4324882 407
2 627284 73 2477394 164
3 1206856 166
4 1278 559
2 558147431 64 2477394 228
2 2210369 82 989800 127
2 713547 4 3799292 69
2 3016965 2 2561766 69
4 1342 539
4 1197 394
4 1342 539
4 1197 394
2 3700021 6 2210369 88
2 7853983 76 989800 209
2 5532601 74 7485100 135
2 8548355 60 4681914 87
3 7581102 59
4 1536 517
2 7898344 5 1317632 210
2 2989754 39 713547 43
3 2477394 228
3 2210369 88
2 9835636 85 5532601 159
2 2548204 65 2989754 104
2 2394522 83 3016965 85
2 3924828 9 1373085 95
2 9595150 31 5532601 190
2 6452016 65 8548355 125
2 6441922 71 9835636 156
2 3839556 65 713547 173
4 1477 313
2 4905916 45 9835636 201
2 390382 11 6452016 76
4 1560 341
2 3746342 31 8548355 167
4 1586 349
2 9564510 83 9353566 546
2 1624064 73 9835636 274
2 4545912 93 3924828 102
2 5681520 5 7853983 81
2 4835714 63 2394522 146
2 3063556 41 5532601 420
2 3090678 19 2548204 84
2 1831640 17 3799292 274
2 6495312 1 3746342 32
3 2477394 -1
2 6902773 90 7898344 95
2 4503903 96 7898344 191
2 4588409 98 4835714 161
2 786676547 96 6495312 97
2 2038333 18 4545912 111
2 4937959 72 2548204 156
2 905537 6 4905916 51
2 4823627 24 6495312 121
4 2310 585
2 5238691 8 4905916 59
2 7754141 70 3839556 135
2 7697735 24 4588409 122
2 25614881 50 3090678 69
3 9564510 83
2 7197842 95 905537 101
2 2661524 81 6902773 171
2 8245510 75 3090678 144
2 83432 5 9703257 83
2 3069882 51 4823627 75
2 2814204 1 4905916 155
2 6370932 89 8930467 125
4 2665 663
3 4905916 155
2 2900615 64 2394522 332
4 2748 782
3 786676547 96
4 3001 994
2 147932 77 6902773 248
2 9653518 75 6495312 151
2 7026352 1 6902773 249
2 9217602 91 1624064 164
2 8128452 1 7754141 71
2 7130550 35 8128452 36
2 4434328 49 25614881 99
2 397635050 95 8548355 413
2 314175752 13 2548204 343
2 3635034 83 4545912 194
3 83432 5
2 9635319 96 9653518 171
2 7918033 2 9653518 173
200
1 20
7411184 33
237531 20
9321858 95
9851157 70
124082308 13
7105279 80
5592310 87
5292953 82
8115416 53
2361827 40
5554474 51
9647197 98
3023340 77
1054599 8
625998366 31
4425313 2
5964864 25
9305579 80
5232978 3
2310693 26
2 4702735 24 5964864 49
2 6239657 58 9647197 156
2 437235 60 237531 80
2 6740461 78 625998366 109
2 7451927 88 5292953 170
2 5055729 78 437235 138
4 1265 129
2 6637577 38 5055729 116
2 8096339 28 2310693 54
2 5625037 58 9305579 138
2 7646967 60 4702735 84
2 8343249 18 5554474 69
2 624842843 40 7451927 128
2 5023125 46 437235 222
2 9126911 8 5964864 117
2 6758169 94 624842843 134
2 981212259 64 9851157 134
3 8343249 18
2 1328492 93 6239657 151
3 1328492 93
2 6536545 26 4425313 28
2 3056761 86 437235 308
2 5581073 90 6637577 128
3 1328492 -1
2 5929154 31 624842843 165
2 4318916 45 3056761 131
2 5405238 51 7451927 304
2 1056280 81 3056761 212
4 1809 266
4 2030 377
4 1986 355
3 5055729 206
2 4713287 60 2361827 100
2 6920097 18 9851157 152
3 8343249 -1
3 6740461 78
2 4631939 52 5625037 110
2 1662717 26 9647197 182
2 9847079 56 5023125 102
2 267465985 42 9851157 194
2 541765145 90 8096339 118
2 8262627 32 9847079 88
2 4032861 70 6758169 164
3 5405238 51
3 6536545 26
2 3428577 14 5625037 124
2 7399417 74 9847079 162
2 304195 52 9847079 214
2 8436123 36 1054599 44
2 595669 6 5292953 411
3 6758169 164
2 1213500 65 624842843 136
2 8199534 15 5232978 18
2 886597008 13 624842843 149
2 9715490 43 5625037 167
2 1651418 67 9126911 75
2 1797138 43 267465985 85
4 2147 238
3 8262627 32
2 1763965 38 4631939 90
2 5744935 8 5929154 39
4 2441 392
2 5853439 88 5744935 96
2 8946647 44 541765145 134
2 1594289 74 3056761 286
4 2470 355
4 2748 567
2 2862197 10 1651418 77
2 1348063 84 1662717 110
2 7371129 14 2862197 24
2 8196291 68 5929154 195
4 2804 468
2 8138139 60 7105279 140
2 2024021 94 7399417 168
2 36896191 16 4318916 61
2 4842841 94 8436123 130
2 1870883 44 7399417 212
2 3032187 60 541765145 194
2 4648117 38 1056280 119
4 2854 386
2 5720013 42 7399417 254
2 5042551 4 1763965 42
2 6433489 94 5929154 289
2 6328411 68 8946647 112
2 9903253 54 3032187 114
2 7530367 24 5720013 66
2 24857 86 8436123 216
2 8390883 76 9847079 462
3 5853439 88
2 562213100 73 24857 159
4 3715 853
2 980836 81 6920097 99
3 4318916 61
4 3468 525
2 5046711 16 5964864 224
2 3154193 46 6433489 140
2 9530395 80 5046711 96
2 3191253 26 886597008 39
2 7260351 20 8946647 132
2 257541593 10 9126911 109
2 8784931 84 3056761 363
2 2919069 66 1651418 157
4 4034 827
2 3000117 18 8138139 78
2 6992031 60 304195 112
2 1043191 96 541765145 432
2 2773969 26 5720013 92
2 3881435 100 4842841 194
4 4414 993
2 7909939 32 8138139 110
2 1263405 30 8946647 162
2 8438103 20 5042551 24
4 3769 449
2 831581 42 1056280 161
2 2135303 84 3032187 198
2 7036897 2 3881435 102
4 4155 583
2 9305849 50 1263405 80
2 2093457 54 3000117 72
2 6744347 52 6328411 120
2 406101 14 24857 173
2 799807 28 8196291 96
2 967329113 46 1797138 89
2 8873635 76 1797138 165
2 2047389 46 8784931 130
4 4883 974
2 418347829 58 8196291 154
2 580689439 32 6328411 152
2 6844089 46 1054599 459
2 4248451 92 8115416 145
2 517288189 50 5046711 146
3 8873635 76
2 8815294 39 6844089 85
2 2061536 97 5744935 105
2 1998962 3 2093457 57
2 9020916 69 9321858 164
3 3428577 14
2 4705865 90 3154193 136
2 9750497 38 7260351 58
2 5111801 94 831581 136
2 9687619 40 1043191 136
2 1197501 26 8138139 193
2 3807335 36 2093457 93
2 5091649 34 1662717 144
2 2417753 74 1662717 218
2 7493923 100 4842841 296
2 847739 4 5042551 28
2 1967285 66 8815294 105
2 6895135 8 9903253 62
4 5255 698
2 1714679 56 4648117 94
2 9933009 66 9750497 104
4 5978 1091
2 2758249 78 7260351 202
2 6189235 60 562213100 133
2 1851147 76 580689439 108
2 3235397 10 7371129 24
2 6470703 64 5720013 156
2 3810121 82 1197501 108
2 1318547 20 5046711 166
2 5423851 100 2024021 194
4 5522 729
2 8151619 92 1851147 168
2 3516093 82 6470703 146
4 6076 951
3 6470703 146
2 7559620 73 1998962 76
3 2135303 84
2 8438105 22 9305849 72
2 2723 36 580689439 236
2 6295453 62 831581 198
2 5098311 16 967329113 62
2 1513505 70 406101 84
2 1851563 56 1043191 192
2 1886595 28 2919069 94
2 4438013 86 6189235 146
2 9779879 24 2758249 102
2 6551553 94 1318547 114
3 1851563 56
2 8134514 47 1513505 117
2 7796 85 8390883 161
2 8804582 59 4713287 119
2 7327816 49 2361827 208
2 648986 55 6992031 115
2 1410908 69 3000117 253
2 6799758 75 8151619 167
2 6052294 95 625998366 126
3 2758249 102
2 9192947 16 9903253 78
3 6744347 52
2 824965820 65 1886595 93
2 7249262 63 5592310 150
2 2556944 17 6799758 92
2 4065186 23 2773969 49
2 2047268 9 3810121 91
3 6470703 -1
2 3844281 90 8815294 195
3 4842841 296
2 598928458 59 3807335 95
300
1 30
7668733 30
5097228 17
1594151 80
6534590 83
877441 38
2958560 81
5660811 76
974834 23
3917253 18
3693684 45
5920687 44
3541094 43
1906633 34
6315208 1
8725395 68
1290650 3
6718861 86
5632348 25
9136183 32
7394062 15
631654161 86
3533360 73
358243099 12
5745090 91
5523925 46
4550852 93
1071167 40
6733238 43
8443481 70
6132120 81
2 7272298 39 358243099 51
2 9117484 29 1071167 69
2 6756574 3 5745090 94
2 4012288 93 4550852 186
2 2168978 31 6132120 112
2 3784468 29 9136183 61
2 1365510 59 3533360 132
2 8250088 81 4550852 267
2 472890 87 2168978 118
2 98720252 21 358243099 72
2 9260334 59 5745090 153
2 5390032 9 9136183 70
4 1735 117
2 2702536 17 8250088 98
2 7414170 15 9117484 44
2 9987676 61 9117484 105
2 4397966 67 6718861 153
2 5000496 29 7414170 44
2 9521602 99 2702536 116
3 8250088 197
2 2548415 52 7394062 67
2 6271449 66 1071167 240
2 1847715 76 5000496 105
2 8853499 72 9987676 133
2 7526581 78 1365510 137
2 6259487 60 2548415 112
4 2085 143
2 977601655 72 7414170 192
2 670289 94 9117484 448
2 2801243 76 6756574 79
2 8747541 30 670289 124
2 866125055 24 98720252 45
2 552857 86 6315208 87
2 3821283 56 1847715 132
2 578677469 82 2168978 200
2 6883335 44 6756574 123
2 2112481 46 866125055 70
2 2948075 48 9987676 181
2 3900965 86 977601655 158
2 5729423 72 866125055 142
3 6271449 66
2 9013288 53 7272298 92
2 3628410 95 5729423 167
2 9061820 13 8747541 43
2 4093678 35 4397966 102
2 5287568 29 670289 166
4 2860 259
2 7695710 31 670289 197
3 4093678 35
2 2104107 8 6315208 95
2 1592549 58 6883335 102
2 7486031 36 9013288 89
2 1534825 42 578677469 124
2 9061043 4 1592549 62
2 7426699 84 7486031 120
2 4376773 50 7695710 81
2 26031 48 2948075 96
2 8586375 24 9260334 83
2 9748193 30 3821283 86
2 3735147 68 8747541 111
4 3581 623
2 8441667 8 3821283 94
2 4479259 56 5390032 65
4 3480 474
2 2597107 20 578677469 144
2 2044781 54 866125055 291
2 6769047 84 8441667 92
2 9213809 2 5000496 285
2 863369 10 4397966 77
2 4574931 72 2548415 184
2 3416909 86 2801243 162
2 5946231 16 2801243 178
2 77377617 18 9013288 191
3 552857 86
2 7057154 27 7426699 111
2 265724420 9 9061043 13
2 9022454 15 7057154 42
4 4153 898
2 62533422 39 578677469 183
2 2848748 97 8586375 121
2 9524254 51 9022454 66
2 5246912 41 9013288 325
2 7899602 79 7426699 256
2 3945556 37 7272298 480
3 5287568 29
2 4779239 72 265724420 81
2 1787713 62 77377617 80
2 9572299 68 265724420 149
2 5284613 26 3735147 94
3 1534825 42
2 6721196 13 2958560 94
2 6047454 27 265724420 176
2 870769408 85 6047454 112
2 2577810 11 62533422 50
2 9412884 77 578677469 229
2 2011654 11 4376773 61
3 2848748 97
2 4940595 40 3416909 126
2 6310445 10 2104107 18
2 6210263 76 9748193 106
2 8971057 58 7899602 137
2 803529 38 3900965 124
2 6076179 88 2104107 106
2 3570829 26 4397966 103
2 1574455 8 4550852 194
2 2123025 54 4479259 110
2 9907611 68 4012288 161
2 5088085 2 6883335 369
2 3381183 72 9748193 178
2 7679705 2 2044781 56
2 8352291 56 9524254 107
2 473368605 14 1290650 17
2 1365319 20 7695710 112
2 1872545 90 4779239 162
2 6939563 40 7486031 446
2 7117797 2 1592549 415
2 1928399 96 870769408 181
2 5737065 62 5284613 88
3 6047454 208
2 4245434 83 5088085 85
2 9688316 65 2104107 171
2 3458606 99 7486031 545
3 9907611 68
3 3735147 156
2 200802 83 9987676 312
2 9931236 13 7117797 15
2 8689372 57 2011654 68
2 1209742 11 7057154 160
4 5855 1331
2 7538118 39 9688316 104
2 8157182 23 7426699 404
2 65777184 85 9213809 87
2 5185176 33 2168978 380
2 3689706 83 9688316 187
2 3286434 11 803529 49
2 6031268 85 9931236 98
2 3358486 91 8157182 114
2 2111096 81 3416909 207
2 5348554 79 5185176 112
2 920844 85 1787713 147
2 133566 11 8352291 67
2 1570272 89 200802 172
2 3317490 7 200802 179
2 115531892 85 6310445 95
2 9821542 63 4574931 135
2 24136 61 7057154 232
2 487706 23 6769047 107
2 7301340 25 5246912 66
2 9981710 7 5348554 86
2 9880240 13 9524254 131
2 6637890 27 4479259 137
2 9983940 85 6721196 98
2 8368566 15 2577810 26
2 1174552 37 6315208 416
2 2829418 43 1574455 51
2 102841004 85 1570272 174
4 5926 926
2 7406116 9 803529 58
2 1660316 45 1365319 65
2 5583566 55 2123025 109
2 7501296 29 9213809 116
2 9794690 47 9524254 178
2 1339780 73 9412884 150
2 6464374 55 24136 116
2 510680 77 4397966 180
2 9902378 87 9931236 185
2 5920748 5 6637890 32
2 8490654 87 1339780 160
2 2098112 97 9022454 290
2 9911992 13 7406116 22
2 9359536 33 4245434 116
2 3306050 51 920844 136
2 5469508 45 1574455 96
2 240737846 11 5523925 57
2 4922648 49 5348554 135
4 7285 1304
2 2918160 81 3286434 92
2 6321698 67 6310445 162
2 918308 85 3286434 177
2 4397846 71 265724420 310
2 4829902 23 24136 139
2 308848 61 9880240 74
2 8096642 59 9931236 244
2 8416772 33 2011654 101
2 3916150 47 2577810 73
2 7902040 61 3381183 133
2 1572010 67 1574455 163
2 6276332 61 6939563 101
2 7018910 71 920844 207
3 6047454 -1
2 2624505 78 9412884 315
2 9790787 92 3358486 183
2 4670269 54 1660316 99
2 7813223 52 5920748 57
3 920844 207
3 6939563 101
2 8913099 12 5946231 28
2 3501701 66 8689372 123
2 8491631 56 7813223 108
2 1998345 58 6031268 143
2 7449683 24 6031268 167
2 8978253 34 487706 57
2 1207013 90 65777184 175
2 661199 24 1872545 114
3 7679705 2
2 6305640 65 6464374 120
2 3622970 55 3286434 232
2 9659516 1 1592549 725
2 4100910 67 115531892 152
2 6523984 77 9790787 169
2 160738 7 2577810 80
3 9688316 187
2 8768223 80 3541094 123
2 287609 58 9880240 132
2 6228675 32 8586375 56
2 6751677 34 6534590 117
2 1313383 68 3416909 275
2 3301569 94 3358486 354
2 9823179 100 2829418 143
2 3561123 4 9061820 17
2 1429277 6 308848 67
2 9517255 76 6228675 108
2 5770785 2 9659516 3
2 3466667 20 1313383 88
2 827877 42 6310445 271
2 8778831 44 200802 308
2 8519017 42 3317490 49
2 3033267 52 510680 129
2 5655725 58 9022454 473
2 9864663 52 1570272 226
2 1312433 62 8416772 95
2 6124347 20 4922648 69
2 7701365 6 3381183 139
2 3721695 36 65777184 211
2 7372153 2 4922648 71
2 9774147 60 6321698 127
3 5469508 45
2 4132428 53 3501701 119
2 966526 95 6210263 171
2 3778720 81 1574455 299
2 5665074 51 8689372 227
2 8271028 53 77377617 133
2 8202790 55 3317490 104
2 4584542 43 8490654 130
4 9874 2014
2 4275606 39 9823179 139
2 1582670 99 8416772 194
2 2167024 61 9659516 64
2 7255528 1 5348554 158
2 3027642 87 9790787 256
2 3263740 45 4779239 231
2 594430766 63 9880240 201
2 9040848 9 7406116 31
2 7601634 63 6721196 161
2 9037412 45 7117797 373
2 9554006 11 308848 78
2 2700984 81 3317490 185
2 8857354 67 1998345 125
2 2619468 13 2801243 412
2 3886334 91 102841004 176
2 100128 57 9794690 104
2 9413170 47 4100910 114
2 704275892 17 65777184 228
2 5992614 47 9412884 405
2 752186888 81 3358486 522
2 6967040 97 4670269 151
2 9644434 23 5770785 25
2 4672276 45 3033267 97
2 2573446 27 8157182 572
2 4993000 33 8096642 92
2 6621626 91 3721695 127
2 1973628 41 8443481 111
2 4810542 95 6076179 183
2 395600 65 8490654 195
2 9032862 35 240737846 46
2 1124288 85 1312433 147
2 3988152 81 9774147 141
2 6269450 35 594430766 98
2 7344834 35 3561123 39
2 6726596 85 4132428 138
2 3399990 55 8768223 135
3 8490654 195
3 7449683 24
2 1814250 59 1124288 144
2 3145004 57 7902040 118
2 2872414 59 2098112 156
2 6556672 53 472890 140
2 5229458 19 6726596 104
2 261712148 93 4574931 228
2 8576262 83 4397846 154
2 7005032 17 1572010 84
2 7640506 75 7255528 76
2 4699772 65 1339780 138
2 1453556 65 6523984 142
2 6274658 59 2829418 241
2 4049636 85 9359536 118
2 532054 31 9774147 172
4 11691 2301
2 4369806 51 2619468 64
400
1 40
5010705 10
4712624 21
8507291 88
5478978 43
5998293 26
998468 77
2775487 48
5895094 83
7008473 82
1165336 1
7779747 60
3742058 43
4298653 82
7844396 85
427077447 96
8852446 55
9590305 26
793216 61
4576683 80
5763730 55
9928037 74
2614164 89
1822287 60
2309126 3
7748073 54
3479016 89
137344307 12
9739834 51
495661 18
1016828 13
8021207 8
8566702 19
2284081 86
5590992 57
2981435 44
5469410 39
9124085 18
6730084 45
4962911 40
8435414 3
2 3389368 17 6730084 62
2 7862282 83 8566702 102
2 4330828 21 6730084 83
2 3040382 19 8435414 22
2 513696 89 1016828 102
2 4592946 11 4298653 93
2 1404724 1 9124085 19
2 4610598 43 3040382 62
2 2002056 53 3479016 142
2 90074 79 3040382 141
2 9573148 85 8566702 187
2 1414222 63 7779747 123
2 7489264 65 8435414 209
2 336384898 19 9739834 70
3 4592946 11
2 3134335 92 4330828 113
2 5653529 98 8566702 285
2 5084515 92 7489264 157
2 9310557 42 3134335 134
2 2379911 100 513696 189
2 2979041 50 2309126 53
2 8003819 76 2379911 176
2 9695269 30 3389368 47
2 3201295 88 4330828 243
2 3184937 86 3040382 227
2 9510515 36 7489264 193
2 1870829 14 3201295 102
2 6354455 68 3389368 115
2 391245681 94 2979041 144
2 7625339 92 2379911 268
2 6786259 56 9124085 75
2 461517 50 513696 407
3 3389368 115
2 3359054 99 5084515 191
2 5149168 93 998468 170
3 3040382 227
2 4014229 50 4962911 90
2 2443821 58 8003819 134
3 5149168 93
2 645236 69 6786259 125
3 3184937 -1
3 6354455 -1
2 9143112 9 4298653 91
2 2076186 31 336384898 50
3 6786259 125
2 9024183 96 9143112 105
2 5732751 24 5653529 122
2 432501673 98 2443821 156
2 3458291 44 336384898 94
2 1087085 2 1165336 3
2 9335063 72 9310557 114
2 9714543 24 1016828 600
2 4778121 38 9739834 183
2 8544723 8 9143112 113
2 6719181 14 3359054 113
2 8963173 82 1404724 83
2 3533647 92 2002056 145
2 2335923 24 4576683 104
2 9068057 98 9573148 183
2 530863 12 9714543 36
2 192207561 62 8544723 70
2 8050529 14 7625339 106
2 6968043 52 391245681 146
2 9565861 14 8544723 84
2 7688381 66 8852446 121
2 4063591 96 530863 108
2 116514625 2 6968043 54
2 4785867 20 8003819 252
2 9794595 56 998468 133
3 2979041 198
4 4146 394
2 8314274 35 2335923 59
2 6193956 1 6719181 15
3 6193956 1
2 163641 2 9565861 16
3 9143112 191
2 2951152 97 336384898 191
4 4183 476
2 2971240 69 8003819 321
2 2070368 49 3134335 255
2 1241458 87 7688381 153
2 2869620 77 3533647 169
3 4610598 -1
2 7824073 78 137344307 90
2 5319519 76 9310557 190
2 92358009 86 2379911 613
2 9097027 88 9794595 144
2 790589 70 9097027 158
2 7084245 66 793216 127
2 9870143 24 7824073 102
2 640345 34 5478978 77
2 7588003 48 5469410 87
2 4993821 6 432501673 104
2 5684021 2 92358009 88
2 8339103 100 432501673 204
2 9335609 34 530863 142
2 4521041 14 4993821 20
2 7006427 92 5732751 116
2 143795 32 9714543 198
2 4700461 6 5732751 122
2 7951575 24 461517 74
2 352817 50 4063591 146
2 4763323 88 530863 280
2 2694291 24 1241458 111
2 2277687 48 461517 122
2 5378705 98 7862282 181
2 9649435 100 7006427 192
3 9510515 36
2 7514180 73 9794595 287
2 3336118 87 9870143 111
2 3259800 33 3533647 202
2 6862736 1 8507291 89
2 9491874 55 9714543 391
2 342820 77 1087085 79
2 4926742 51 1414222 114
2 9787896 49 3458291 93
2 4705226 55 4778121 93
2 2604172 53 7688381 230
2 6450308 45 9794595 332
2 3705974 7 6450308 52
3 4014229 50
2 6599473 78 5319519 154
2 378567995 52 3458291 145
2 879733 34 9870143 145
2 8456543 96 7514180 169
2 591667833 22 8339103 122
2 7637915 36 3705974 43
2 5863253 54 2971240 123
2 847045183 44 432501673 284
2 8792921 14 7084245 80
2 7106161 94 4785867 114
2 819835 32 591667833 54
3 8792921 14
2 4329818 3 5084515 208
2 8925596 17 9335609 51
2 1637838 95 7688381 325
2 194994032 53 2951152 150
2 4037378 95 4521041 109
3 8050529 14
2 909951 76 8963173 158
2 703365529 66 3705974 109
3 1087085 79
2 7055274 71 4778121 164
2 504696172 9 4521041 118
2 6368286 23 4700461 29
2 3171776 81 4330828 613
3 7951575 24
3 4705226 55
2 1769044 65 4778121 174
2 3557830 99 1637838 194
2 1337982 95 9590305 121
3 194994032 53
2 8010775 36 143795 68
2 486276721 26 1241458 137
2 2354683 32 1016828 1747
2 9207605 42 137344307 277
2 5274573 42 7106161 136
2 4576997 22 8314274 57
2 186959 68 1769044 133
3 5863253 54
2 4397758 95 9491874 150
2 8085088 89 1637838 283
3 9794595 537
2 9590755 100 92358009 188
2 6380381 46 9335609 97
2 2376327 100 6368286 123
2 7307871 44 4926742 95
2 2815737 34 6368286 157
2 3004867 64 4785867 220
2 1135805 6 5378705 104
2 6260199 64 4576997 86
2 2287553 10 486276721 36
3 9207605 42
2 672690 91 8010775 127
2 1815274 55 186959 123
2 3478444 69 847045183 113
2 4543070 39 3336118 126
2 7988992 85 8339103 239
3 186959 123
2 507621 22 7625339 114
2 257615 32 879733 66
3 6599473 78
2 3763390 27 6862736 28
3 8339103 239
3 2694291 24
2 8623448 5 2443821 398
2 681770 95 640345 129
2 2647148 45 2775487 93
2 8123934 7 2647148 52
2 7834816 57 4397758 152
2 9826770 95 9124085 272
2 5737098 79 6862736 107
2 41932 77 257615 109
4 6878 743
2 8420986 3 4763323 91
3 4592946 -1
2 152599 28 5469410 115
2 6439025 90 3478444 159
2 9136507 24 879733 167
3 2376327 100
2 8714660 37 4329818 40
2 2597398 75 8085088 164
2 1916920 73 41932 150
2 1880138 27 378567995 79
2 5578508 25 9491874 232
2 5777086 43 5274573 85
2 789856 89 3478444 248
2 6223730 27 3171776 108
2 7153780 49 6380381 95
2 3614694 3 672690 94
2 4008790 47 1916920 120
3 7834816 57
2 8657219 36 4763323 127
2 8111293 10 1880138 37
2 4791271 12 7779747 230
2 2606145 78 7307871 122
2 5457625 10 1337982 105
2 620579 8 6730084 615
2 559901 34 7307871 156
2 56065619 48 1637838 406
2 654577229 90 5469410 205
2 5955831 12 3259800 45
3 681770 95
2 7909360 69 3171776 177
2 5657602 43 1337982 148
2 685572 37 6380381 132
2 6918902 23 6223730 50
2 5174232 53 352817 103
2 8860586 7 3259800 52
2 700908 29 879733 316
2 448481950 11 2647148 63
2 9217600 1 1916920 121
2 229634616 5 8010775 135
2 1375754 47 1916920 168
2 798970188 29 6380381 161
2 4742980 85 789856 174
2 270902 83 9217600 84
2 483383320 49 3171776 249
2 8537322 19 7055274 90
2 6865964 17 1769044 82
2 9771870 63 41932 391
2 8446208 81 6862736 188
2 6544274 3 3336118 129
2 6689940 69 3004867 133
2 5749004 81 8111293 91
3 6862736 188
2 2045569 90 4791271 102
2 5029131 100 2951152 197
2 7818565 22 8010775 157
2 1576495 8 1337982 156
2 8758985 30 1135805 36
2 7953939 40 483383320 89
2 306108557 10 507621 32
3 5578508 25
2 173966 55 1880138 173
2 3461680 25 5955831 37
2 9331906 43 229634616 48
3 879733 510
2 839964991 96 3557830 195
2 4582489 14 1769044 96
2 4926705 86 7779747 518
2 2619899 32 8758985 62
2 7191713 30 672690 124
2 5901611 80 9310557 270
2 619915237 70 4926742 277
2 8824061 6 2070368 55
2 5677351 8 8758985 70
2 4519809 54 8860586 61
2 627353 2 6865964 19
2 5886691 8 4778121 234
2 7075293 94 789856 268
2 7485941 26 620579 34
2 4469727 68 7818565 90
2 3951653 22 3461680 47
2 4816829 50 6368286 107
2 8588391 28 1165336 29
2 197057 26 152599 54
2 6175383 56 6223730 106
2 2620657 14 8420986 17
2 4895483 92 7485941 118
2 8244051 28 197057 54
2 1560781 66 5174232 119
2 375535863 12 56065619 60
2 2038609 14 2309126 17
2 5338345 22 7191713 52
2 962010163 8 3461680 55
2 7122989 82 4962911 122
2 418903 24 7485941 142
2 2817201 74 5338345 96
2 2295739 4 6865964 23
2 118753 90 7824073 321
2 2998777 46 1769044 148
2 2167313 30 7075293 124
2 9306651 68 5955831 135
2 9011285 22 8435414 335
2 8295871 8 152599 90
2 7160537 98 8657219 134
2 1755505 6 8925596 23
2 4978939 48 8714660 85
2 1270965 58 685572 95
4 11143 2955
2 8768299 20 9491874 170
2 2058085 70 2647148 133
2 1359439 24 559901 58
2 6530281 14 685572 109
2 9178753 94 3614694 97
2 7561227 36 7191713 162
2 9648709 30 4298653 112
4 10480 2168
2 9132253 58 6223730 164
2 7976199 32 685572 141
4 9848 1478
2 2351455 68 4926705 154
2 4986105 18 9335609 340
2 2933009 90 8111293 181
2 7007515 96 3951653 118
3 8768299 20
2 7184196 97 2443821 883
2 5981750 11 2998777 57
2 3529140 21 448481950 32
2 6021158 71 6439025 161
2 192264 5 7953939 45
2 909452800 5 8657219 139
2 2934862 71 1404724 230
2 401344780 81 9306651 149
2 9387710 75 7055274 165
3 4926705 154
2 8905739 92 2076186 123
2 959384773 10 7976199 42
2 6332381 38 6689940 107
3 685572 151
2 6750622 47 2934862 118
2 7561280 49 3529140 70
2 4385720 17 962010163 25
2 8486576 49 1560781 115
3 8792921 -1
2 7112661 38 5274573 123
2 4568895 40 4385720 57
2 8498137 6 627353 8
3 1880138 263
2 3333226 3 7485941 145
2 5847468 45 9331906 88
2 3861156 5 2058085 75
2 1661206 99 654577229 189
2 4097614 47 8537322 66
2 2892400 5 306108557 15
2 576607618 83 559901 141
4 10634 1675
2 9485370 39 2045569 129
4 11175 2177
2 3897304 57 7006427 249
2 8741930 3 8295871 11
2 8673388 61 620579 214
2 4233886 35 448481950 116
2 9199040 81 3529140 151
2 2730936 69 1576495 77
2 406410 3 7184196 100
2 9465036 37 1135805 113
2 9605152 53 401344780 134
2 8745880 57 9573148 240
2 151531754 15 7075293 139
2 1280044 37 2620657 51
2 2473054 83 9465036 120
2 597888 21 118753 111
3 6439025 161
2 7719171 48 4962911 170
2 4626173 90 2620657 141
4 12889 3286
2 2643221 10 839964991 106
3 4926705 -1
2 2969974 95 2038609 109
2 5802584 49 9648709 79
2 2490538 63 6260199 127
2 4067938 7 909452800 12
2 2131812 21 8537322 87
2 7218262 51 9387710 126
3 229634616 93
2 2559683 100 8244051 128
2 3612477 34 576607618 117
2 51848295 12 5457625 22
2 1995073 6 5457625 28
2 6418009 30 7191713 192
2 9073571 12 6689940 119
2 987610141 90 2473054 173
3 9387710 126
2 3218270 67 7184196 167
3 9306651 202
2 8304683 80 8905739 172
2 477819109 46 7184196 213
2 763422287 28 4763323 406
3 7834816 -1
2 162280 81 6544274 84
2 4746426 59 7160537 157
2 748191612 61 6750622 108
2 8193706 3 597888 24
2 5300076 29 378567995 81
2 7097758 59 7561280 108
2 3040832 85 7153780 134
2 8843090 27 4233886 62
*** Solution
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Solution {
private final static int CMD_INIT = 1;
private final static int CMD_ADD = 2;
private final static int CMD_REMOVE = 3;
private final static int CMD_DISTRIBUTE = 4;
private final static UserSolution usersolution = new UserSolution();
private static boolean run(BufferedReader br) throws Exception {
int q = Integer.parseInt(br.readLine());
int[] midArr = new int[1000];
int[] mnumArr = new int[1000];
int mid, mnum, mparent, n, k;
int cmd, ans, ret = 0;
boolean okay = false;
for (int i = 0; i < q; ++i) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
cmd = Integer.parseInt(st.nextToken());
switch (cmd) {
case CMD_INIT:
n = Integer.parseInt(st.nextToken());
for (int j = 0; j < n; ++j) {
StringTokenizer dep = new StringTokenizer(br.readLine(), " ");
midArr[j] = Integer.parseInt(dep.nextToken());
mnumArr[j] = Integer.parseInt(dep.nextToken());
}
usersolution.init(n, midArr, mnumArr);
okay = true;
break;
case CMD_ADD:
mid = Integer.parseInt(st.nextToken());
mnum = Integer.parseInt(st.nextToken());
mparent = Integer.parseInt(st.nextToken());
ans = Integer.parseInt(st.nextToken());
ret = usersolution.add(mid, mnum, mparent);
if (ret != ans)
okay = false;
break;
case CMD_REMOVE:
mid = Integer.parseInt(st.nextToken());
ans = Integer.parseInt(st.nextToken());
ret = usersolution.remove(mid);
if (ret != ans)
okay = false;
break;
case CMD_DISTRIBUTE:
k = Integer.parseInt(st.nextToken());
ans = Integer.parseInt(st.nextToken());
ret = usersolution.distribute(k);
if (ret != ans)
okay = false;
break;
default:
okay = false;
break;
}
}
return okay;
}
public static void main(String[] args) throws Exception {
int TC, MARK;
System.setIn(new java.io.FileInputStream("sample_input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
TC = Integer.parseInt(st.nextToken());
MARK = Integer.parseInt(st.nextToken());
for (int testcase = 1; testcase <= TC; ++testcase) {
int score = run(br) ? MARK : 0;
System.out.println("#" + testcase + " " + score);
}
br.close();
}
}
*** UserSolution
import java.util.*;
class Node {
int id, num, child;
Node parent;
boolean deleted;
Node (int id, int num){
this.id = id;
this.num = num;
}
}
class UserSolution {
int N;
Map<Integer, Node> mapNode;
int IDs[];
public void init(int N, int mId[], int mNum[]) {
mapNode = new HashMap<>();
this.N = N;
IDs = new int[N];
mapNode.clear();
for (int i = 0; i < N; i++){
IDs[i] = mId[i];
Node n = new Node(mId[i], mNum[i]);
mapNode.put(mId[i], n);
}
}
public int add(int mId, int mNum, int mParent) {
Node n = new Node(mId, mNum);
Node parent = mapNode.get(mParent);
if (parent.child >= 3) return -1;
mapNode.put(mId, n);
n.parent = parent;
int res = -1;
while(n.parent != null){
n = n.parent;
n.num += mNum;
if (res == -1){
res = n.num;
n.child++;
}
}
return res;
}
public int remove(int mId) {
Node n = mapNode.get(mId);
if (n == null || n.deleted) return -1;
n.deleted = true;
Node parent = n.parent;
parent.child--;
while(parent != null){
if (parent.deleted) return -1;
parent.num -= n.num;
parent = parent.parent;
}
return n.num;
}
public int distribute(int K) {
int left = 0;
int right = 0;
for (int i = 0; i < N; i++){
Node n = mapNode.get(IDs[i]);
if (n.deleted) continue;
if (right < n.num) right = n.num;
}
int L = 0;
while (left <= right){
int mid = (left + right)/2;
int sum = 0;
for (int i = 0; i < N; i++){
Node n = mapNode.get(IDs[i]);
if (n.deleted) continue;
sum += Math.min(mid, n.num);
if (sum > K) break;
}
if (sum <= K) {
L = mid;
left = mid + 1;
}else right = mid - 1;
}
return L;
}
}