Connection Status:
Competition Arena > DismantleTheTree

DismantleTheTree

2019 Humblefool Cup Prelims · 2019-03-12 · by ashisha690

2019 Humblefool Cup Prelims · 2019-03-12 · by ashisha690 · Graph Theory
Class Name: DismantleTheTree
Return Type: int
Method Name: dismantle
Arg Types: (int, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

We have a weighted tree with N nodes, numbered 1 through N. You are given the description of the tree: the int[]s X, Y and edgeWeight, each with N-1 elements. For each i between 0 and N-2, inclusive, there is an edge that connects the nodes X[i] and Y[i], and the weight of this edge is edgeWeight[i].

You want to erase all edges of the tree as cheaply as possible. In each step, you can select any simple path that consists of edges of the same weight W, pay W, and erase all the edges that form the path.

(Note that you only pay W once, regardless of the length of the path. Also note that the entire path must still exist in the tree.)

Compute and return the minimum total cost you need to pay to erase all edges of the given tree.

Constraints

  • N will be between 2 and 1000, inclusive.
  • X, Y, and edgeWeight will each contain exactly N-1 elements.
  • All elements of X and Y will be between 1 and N, inclusive.
  • All elements of edgeWeight will be between 1 and 100, inclusive.
  • It is guaranteed that the input will be a tree.
Examples
0)
500
{450 ,11 ,460 ,386 ,3 ,97 ,439 ,288 ,433 ,444 ,379 ,97 ,121 ,115 ,500 ,196 ,264 ,421 ,254 ,64 ,462 ,413 ,254 ,253 ,334 ,40 ,404 ,24 ,362 ,379 ,128 ,258 ,179 ,468 ,379 ,134 ,78 ,286 ,344 ,422 ,464 ,130 ,281 ,63 ,285 ,477 ,409 ,386 ,298 ,144 ,262 ,89 ,203 ,268 ,315 ,201 ,453 ,97 ,395 ,256 ,65 ,141 ,294 ,13 ,97 ,29 ,342 ,323 ,296 ,98 ,212 ,390 ,241 ,387 ,43 ,205 ,122 ,477 ,484 ,177 ,280 ,15 ,320 ,337 ,268 ,314 ,62 ,253 ,337 ,167 ,307 ,399 ,205 ,143 ,228 ,365 ,117 ,272 ,496 ,196 ,159 ,317 ,398 ,272 ,471 ,89 ,431 ,417 ,27 ,36 ,468 ,399 ,288 ,120 ,83 ,62 ,43 ,13 ,46 ,236 ,80 ,159 ,421 ,123 ,128 ,50 ,460 ,331 ,477 ,500 ,413 ,463 ,136 ,388 ,236 ,201 ,345 ,154 ,166 ,217 ,115 ,177 ,65 ,161 ,454 ,408 ,471 ,192 ,134 ,412 ,131 ,217 ,11 ,346 ,333 ,223 ,223 ,111 ,360 ,454 ,437 ,299 ,451 ,179 ,464 ,499 ,117 ,337 ,11 ,65 ,171 ,320 ,16 ,438 ,144 ,285 ,111 ,500 ,183 ,269 ,130 ,60 ,136 ,13 ,392 ,30 ,60 ,442 ,360 ,424 ,402 ,482 ,321 ,496 ,407 ,488 ,59 ,368 ,230 ,117 ,450 ,24 ,27 ,181 ,65 ,162 ,409 ,320 ,265 ,386 ,395 ,102 ,343 ,450 ,205 ,117 ,236 ,441 ,294 ,32 ,4 ,477 ,382 ,244 ,36 ,239 ,460 ,480 ,330 ,77 ,246 ,33 ,328 ,147 ,280 ,124 ,487 ,37 ,112 ,313 ,53 ,241 ,98 ,408 ,196 ,451 ,127 ,89 ,281 ,254 ,269 ,372 ,269 ,54 ,131 ,132 ,322 ,375 ,299 ,312 ,431 ,409 ,352 ,310 ,130 ,40 ,379 ,117 ,447 ,422 ,121 ,72 ,148 ,435 ,159 ,157 ,105 ,238 ,65 ,346 ,168 ,393 ,13 ,117 ,93 ,189 ,117 ,390 ,327 ,284 ,392 ,357 ,327 ,117 ,346 ,10 ,337 ,131 ,389 ,456 ,464 ,313 ,79 ,24 ,226 ,217 ,293 ,414 ,314 ,447 ,295 ,372 ,408 ,357 ,286 ,379 ,169 ,352 ,356 ,386 ,111 ,144 ,489 ,337 ,143 ,211 ,15 ,163 ,272 ,6 ,123 ,122 ,353 ,52 ,121 ,442 ,382 ,167 ,467 ,396 ,372 ,10 ,12 ,187 ,81 ,12 ,258 ,280 ,467 ,322 ,78 ,500 ,94 ,254 ,379 ,298 ,157 ,368 ,456 ,144 ,184 ,207 ,268 ,12 ,258 ,177 ,398 ,338 ,105 ,437 ,211 ,217 ,162 ,396 ,408 ,395 ,280 ,97 ,23 ,43 ,254 ,476 ,314 ,348 ,236 ,285 ,426 ,250 ,327 ,2 ,11 ,313 ,193 ,111 ,191 ,3 ,417 ,378 ,241 ,150 ,413 ,37 ,454 ,391 ,500 ,171 ,236 ,97 ,361 ,188 ,280 ,379 ,328 ,312 ,181 ,288 ,102 ,69 ,83 ,154 ,384 ,378 ,136 ,386 ,439 ,399 ,368 ,179 ,410 ,437 ,313 ,375 ,349 ,321 ,368 ,349 ,189 ,346 ,500 ,478 ,65 ,111 ,168 ,65 ,253 ,310 ,196 ,230 ,330 ,201 ,417 ,437 ,196 ,288 ,318 ,42 ,58 ,269 ,395 ,202 ,258 ,202 ,101 ,464 ,378 ,285 ,184 ,285 ,383 ,352 ,379 ,72 ,374 ,365 ,29 ,117 ,276 ,432 ,365 ,409 ,357 ,479 ,168 ,294 ,92 ,431 ,452 ,500 ,471 ,221 ,353 ,378 ,179 ,330 ,368 ,442 ,61 ,320 ,408 }
{1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 ,19 ,20 ,21 ,22 ,23 ,24 ,25 ,26 ,27 ,28 ,29 ,30 ,31 ,32 ,33 ,34 ,35 ,36 ,37 ,38 ,39 ,40 ,41 ,42 ,43 ,44 ,45 ,46 ,47 ,48 ,49 ,50 ,51 ,52 ,53 ,54 ,55 ,56 ,57 ,58 ,59 ,60 ,61 ,62 ,63 ,64 ,65 ,66 ,67 ,68 ,69 ,70 ,71 ,72 ,73 ,74 ,75 ,76 ,77 ,78 ,79 ,80 ,81 ,82 ,83 ,84 ,85 ,86 ,87 ,88 ,89 ,90 ,91 ,92 ,93 ,94 ,95 ,96 ,97 ,98 ,99 ,100 ,101 ,102 ,103 ,104 ,105 ,106 ,107 ,108 ,109 ,110 ,111 ,112 ,113 ,114 ,115 ,116 ,118 ,119 ,120 ,121 ,122 ,123 ,124 ,125 ,126 ,127 ,128 ,129 ,130 ,131 ,132 ,133 ,134 ,135 ,136 ,137 ,138 ,139 ,140 ,141 ,142 ,143 ,144 ,145 ,146 ,147 ,148 ,149 ,150 ,151 ,152 ,153 ,154 ,155 ,156 ,157 ,158 ,159 ,160 ,161 ,162 ,163 ,164 ,165 ,166 ,167 ,168 ,169 ,170 ,171 ,172 ,173 ,174 ,175 ,176 ,177 ,178 ,179 ,180 ,181 ,182 ,183 ,184 ,185 ,186 ,187 ,188 ,189 ,190 ,191 ,192 ,193 ,194 ,195 ,196 ,197 ,198 ,199 ,200 ,201 ,202 ,203 ,204 ,205 ,206 ,207 ,208 ,209 ,210 ,211 ,212 ,213 ,214 ,215 ,216 ,217 ,218 ,219 ,220 ,221 ,222 ,223 ,224 ,225 ,226 ,227 ,228 ,229 ,230 ,231 ,232 ,233 ,234 ,235 ,236 ,237 ,238 ,239 ,240 ,241 ,242 ,243 ,244 ,245 ,246 ,247 ,248 ,249 ,250 ,251 ,252 ,253 ,254 ,255 ,256 ,257 ,258 ,259 ,260 ,261 ,262 ,263 ,264 ,265 ,266 ,267 ,268 ,269 ,270 ,271 ,272 ,273 ,274 ,275 ,276 ,277 ,278 ,279 ,280 ,281 ,282 ,283 ,284 ,285 ,286 ,287 ,288 ,289 ,290 ,291 ,292 ,293 ,294 ,295 ,296 ,297 ,298 ,299 ,300 ,301 ,302 ,303 ,304 ,305 ,306 ,307 ,308 ,309 ,310 ,311 ,312 ,313 ,314 ,315 ,316 ,317 ,318 ,319 ,320 ,321 ,322 ,323 ,324 ,325 ,326 ,327 ,328 ,329 ,330 ,331 ,332 ,333 ,334 ,335 ,336 ,337 ,338 ,339 ,340 ,341 ,342 ,343 ,344 ,345 ,346 ,347 ,348 ,349 ,350 ,351 ,352 ,353 ,354 ,355 ,356 ,357 ,358 ,359 ,360 ,361 ,362 ,363 ,364 ,365 ,366 ,367 ,368 ,369 ,370 ,371 ,372 ,373 ,374 ,375 ,376 ,377 ,378 ,379 ,380 ,381 ,382 ,383 ,384 ,385 ,386 ,387 ,388 ,389 ,390 ,391 ,392 ,393 ,394 ,395 ,396 ,397 ,398 ,399 ,400 ,401 ,402 ,403 ,404 ,405 ,406 ,407 ,408 ,409 ,410 ,411 ,412 ,413 ,414 ,415 ,416 ,417 ,418 ,419 ,420 ,421 ,422 ,423 ,424 ,425 ,426 ,427 ,428 ,429 ,430 ,431 ,432 ,433 ,434 ,435 ,436 ,437 ,438 ,439 ,440 ,441 ,442 ,443 ,444 ,445 ,446 ,447 ,448 ,449 ,450 ,451 ,452 ,453 ,454 ,455 ,456 ,457 ,458 ,459 ,460 ,461 ,462 ,463 ,464 ,465 ,466 ,467 ,468 ,469 ,470 ,471 ,472 ,473 ,474 ,475 ,476 ,477 ,478 ,479 ,480 ,481 ,482 ,483 ,484 ,485 ,486 ,487 ,488 ,489 ,490 ,491 ,492 ,493 ,494 ,495 ,496 ,497 ,498 ,499 ,500 }
{50 ,17 ,21 ,42 ,29 ,10 ,2 ,8 ,7 ,20 ,12 ,15 ,37 ,47 ,19 ,3 ,10 ,22 ,6 ,35 ,30 ,12 ,23 ,19 ,43 ,12 ,17 ,4 ,13 ,10 ,30 ,28 ,34 ,44 ,3 ,26 ,5 ,43 ,14 ,8 ,22 ,40 ,45 ,23 ,30 ,35 ,38 ,10 ,9 ,44 ,44 ,22 ,23 ,38 ,24 ,38 ,14 ,15 ,31 ,28 ,36 ,25 ,14 ,48 ,48 ,17 ,38 ,47 ,47 ,4 ,4 ,17 ,26 ,36 ,45 ,23 ,11 ,48 ,39 ,5 ,37 ,11 ,44 ,27 ,43 ,20 ,8 ,45 ,23 ,36 ,22 ,10 ,11 ,5 ,40 ,3 ,26 ,2 ,42 ,23 ,31 ,39 ,13 ,1 ,27 ,27 ,11 ,30 ,35 ,49 ,3 ,38 ,44 ,40 ,48 ,24 ,33 ,20 ,21 ,6 ,27 ,39 ,1 ,6 ,1 ,20 ,43 ,42 ,13 ,40 ,22 ,20 ,47 ,1 ,37 ,27 ,16 ,14 ,11 ,49 ,22 ,47 ,22 ,11 ,7 ,12 ,33 ,17 ,16 ,7 ,4 ,15 ,12 ,49 ,50 ,35 ,24 ,36 ,46 ,17 ,22 ,6 ,35 ,6 ,38 ,3 ,5 ,39 ,15 ,16 ,29 ,9 ,45 ,13 ,8 ,38 ,49 ,40 ,22 ,39 ,46 ,39 ,32 ,31 ,20 ,13 ,45 ,11 ,41 ,34 ,46 ,14 ,10 ,6 ,44 ,2 ,25 ,22 ,46 ,15 ,14 ,25 ,30 ,25 ,4 ,40 ,37 ,30 ,40 ,23 ,29 ,27 ,2 ,40 ,26 ,17 ,43 ,39 ,7 ,33 ,2 ,45 ,15 ,45 ,18 ,10 ,27 ,20 ,33 ,49 ,49 ,8 ,25 ,45 ,16 ,29 ,34 ,17 ,2 ,26 ,24 ,26 ,48 ,9 ,33 ,35 ,49 ,35 ,33 ,24 ,7 ,5 ,13 ,43 ,33 ,17 ,35 ,36 ,15 ,17 ,18 ,24 ,5 ,5 ,23 ,9 ,27 ,34 ,23 ,2 ,25 ,3 ,1 ,14 ,17 ,43 ,20 ,3 ,48 ,35 ,42 ,48 ,27 ,41 ,42 ,3 ,1 ,24 ,36 ,42 ,25 ,35 ,19 ,44 ,34 ,50 ,41 ,42 ,24 ,29 ,46 ,27 ,27 ,34 ,8 ,19 ,7 ,46 ,34 ,27 ,39 ,48 ,41 ,32 ,15 ,27 ,50 ,8 ,50 ,38 ,24 ,39 ,38 ,23 ,16 ,31 ,20 ,28 ,20 ,32 ,46 ,15 ,38 ,43 ,16 ,42 ,11 ,37 ,25 ,18 ,46 ,31 ,48 ,9 ,30 ,49 ,35 ,46 ,35 ,23 ,5 ,34 ,5 ,42 ,21 ,21 ,38 ,17 ,10 ,49 ,18 ,4 ,43 ,26 ,22 ,48 ,5 ,35 ,38 ,6 ,42 ,42 ,43 ,16 ,6 ,47 ,17 ,28 ,39 ,38 ,17 ,16 ,3 ,39 ,49 ,7 ,34 ,22 ,34 ,47 ,26 ,8 ,4 ,32 ,7 ,32 ,28 ,12 ,37 ,46 ,50 ,24 ,30 ,44 ,19 ,34 ,23 ,9 ,23 ,22 ,34 ,43 ,16 ,32 ,41 ,15 ,21 ,31 ,15 ,43 ,28 ,5 ,26 ,37 ,1 ,32 ,34 ,10 ,18 ,17 ,6 ,7 ,37 ,20 ,17 ,43 ,33 ,14 ,11 ,33 ,43 ,13 ,33 ,48 ,38 ,28 ,34 ,1 ,32 ,31 ,25 ,46 ,2 ,26 ,27 ,47 ,26 ,28 ,15 ,4 ,7 ,31 ,6 ,19 ,18 ,40 ,17 ,41 ,14 ,14 ,32 ,21 ,33 ,46 ,21 ,3 ,16 ,29 ,43 ,23 ,6 ,12 ,1 ,26 ,42 ,14 ,28 ,38 ,1 ,21 ,44 ,40 ,6 ,50 ,46 ,48 ,12 ,34 ,25 }
Returns: 12450
1)
4
{1, 2, 2}
{2, 3, 4}
{1, 2, 1}
Returns: 3

The tree looks as follows: 1 | |[1] | 3-------2-------4 [2] [1] In the optimal solution we pay 1 to remove the path 1-2-4 and then we pay 2 to remove the edge 2-3.

2)
100
{23 ,36 ,93 ,89 ,34 ,68 ,4 ,58 ,63 ,15 ,57 ,6 ,64 ,13 ,69 ,26 ,73 ,73 ,45 ,47 ,70 ,54 ,62 ,58 ,48 ,79 ,55 ,54 ,45 ,26 ,18 ,43 ,66 ,2 ,79 ,69 ,45 ,56 ,13 ,14 ,17 ,27 ,73 ,89 ,100 ,61 ,90 ,36 ,97 ,48 ,68 ,88 ,88 ,76 ,80 ,29 ,39 ,89 ,97 ,79 ,79 ,76 ,90 ,76 ,47 ,90 ,90 ,48 ,54 ,78 ,54 ,82 ,80 ,68 ,65 ,49 ,63 ,54 ,48 ,89 ,76 ,97 ,60 ,15 ,44 ,65 ,72 ,82 ,94 ,88 ,2 ,79 ,82 ,100 ,80 ,54 ,17 ,70 ,69 }
{1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 ,19 ,20 ,21 ,22 ,23 ,24 ,25 ,26 ,27 ,28 ,29 ,30 ,31 ,32 ,33 ,34 ,35 ,36 ,37 ,38 ,39 ,40 ,41 ,42 ,43 ,44 ,45 ,46 ,47 ,48 ,49 ,50 ,51 ,52 ,53 ,54 ,55 ,56 ,57 ,58 ,59 ,60 ,61 ,62 ,63 ,64 ,65 ,66 ,67 ,68 ,69 ,70 ,71 ,72 ,73 ,74 ,75 ,77 ,78 ,79 ,80 ,81 ,82 ,83 ,84 ,85 ,86 ,87 ,88 ,89 ,90 ,91 ,92 ,93 ,94 ,95 ,96 ,97 ,98 ,99 ,100 }
{4 ,4 ,5 ,1 ,2 ,2 ,3 ,2 ,3 ,4 ,5 ,2 ,4 ,2 ,5 ,5 ,1 ,4 ,2 ,1 ,2 ,2 ,2 ,4 ,4 ,2 ,2 ,5 ,1 ,3 ,1 ,4 ,3 ,4 ,1 ,5 ,5 ,1 ,5 ,4 ,2 ,2 ,3 ,3 ,2 ,4 ,2 ,2 ,2 ,2 ,4 ,4 ,4 ,3 ,3 ,1 ,2 ,3 ,5 ,3 ,3 ,5 ,1 ,1 ,1 ,3 ,2 ,5 ,5 ,4 ,5 ,4 ,4 ,1 ,5 ,3 ,3 ,2 ,1 ,4 ,2 ,1 ,5 ,5 ,4 ,3 ,4 ,4 ,3 ,4 ,4 ,1 ,5 ,5 ,1 ,2 ,1 ,1 ,1 }
Returns: 215
3)
5
{1 ,1 ,5 ,3 }
{2 ,3 ,4 ,5 }
{2 ,2 ,2 ,1 }
Returns: 5

The tree looks as follows: [2] [2] [1] [2] 2-------1-------3-------5-------4 Note that we cannot erase all the edges with weight 2 at the same time, as they don't form a single simple path.

4)
500
{141 ,384 ,383 ,280 ,88 ,193 ,213 ,40 ,212 ,29 ,456 ,384 ,34 ,333 ,88 ,129 ,172 ,115 ,139 ,57 ,197 ,82 ,206 ,108 ,365 ,274 ,472 ,48 ,27 ,84 ,365 ,415 ,226 ,493 ,349 ,358 ,244 ,294 ,34 ,333 ,282 ,147 ,9 ,63 ,301 ,227 ,59 ,187 ,91 ,194 ,139 ,362 ,79 ,51 ,460 ,358 ,26 ,270 ,188 ,92 ,368 ,495 ,234 ,13 ,84 ,13 ,231 ,323 ,83 ,328 ,316 ,340 ,458 ,26 ,7 ,221 ,364 ,225 ,63 ,276 ,297 ,63 ,293 ,95 ,147 ,53 ,427 ,214 ,224 ,188 ,180 ,70 ,422 ,276 ,164 ,413 ,222 ,422 ,448 ,162 ,371 ,338 ,187 ,456 ,448 ,81 ,68 ,232 ,211 ,330 ,442 ,147 ,234 ,176 ,484 ,303 ,206 ,423 ,417 ,431 ,358 ,311 ,240 ,83 ,282 ,166 ,453 ,37 ,225 ,51 ,209 ,150 ,431 ,445 ,69 ,147 ,51 ,150 ,62 ,418 ,176 ,169 ,92 ,352 ,83 ,310 ,27 ,444 ,34 ,38 ,398 ,128 ,449 ,100 ,254 ,316 ,268 ,478 ,30 ,310 ,370 ,264 ,27 ,283 ,158 ,228 ,90 ,423 ,448 ,147 ,269 ,363 ,319 ,488 ,40 ,30 ,273 ,157 ,236 ,99 ,185 ,248 ,269 ,368 ,272 ,344 ,297 ,424 ,79 ,97 ,13 ,443 ,274 ,386 ,100 ,460 ,324 ,203 ,406 ,195 ,276 ,223 ,83 ,180 ,394 ,302 ,99 ,82 ,391 ,139 ,352 ,25 ,34 ,460 ,84 ,150 ,379 ,494 ,317 ,499 ,453 ,40 ,118 ,312 ,317 ,475 ,14 ,139 ,106 ,128 ,244 ,404 ,5 ,95 ,217 ,495 ,177 ,310 ,323 ,338 ,255 ,406 ,293 ,66 ,317 ,62 ,244 ,404 ,300 ,291 ,343 ,323 ,491 ,481 ,4 ,79 ,341 ,282 ,223 ,206 ,341 ,352 ,25 ,353 ,391 ,5 ,260 ,244 ,378 ,206 ,296 ,304 ,34 ,417 ,13 ,163 ,207 ,254 ,467 ,295 ,424 ,17 ,433 ,260 ,270 ,160 ,365 ,232 ,79 ,312 ,476 ,378 ,30 ,51 ,304 ,244 ,212 ,495 ,350 ,188 ,217 ,39 ,274 ,343 ,248 ,405 ,378 ,219 ,34 ,292 ,30 ,177 ,195 ,350 ,405 ,214 ,133 ,255 ,365 ,244 ,419 ,293 ,295 ,121 ,397 ,214 ,368 ,64 ,139 ,88 ,467 ,52 ,433 ,432 ,84 ,419 ,382 ,269 ,475 ,80 ,442 ,145 ,8 ,334 ,15 ,470 ,480 ,427 ,4 ,124 ,80 ,118 ,423 ,450 ,500 ,304 ,119 ,292 ,316 ,495 ,394 ,453 ,261 ,310 ,333 ,281 ,424 ,372 ,494 ,294 ,280 ,318 ,80 ,147 ,379 ,26 ,34 ,80 ,464 ,114 ,442 ,88 ,306 ,184 ,413 ,151 ,417 ,50 ,268 ,188 ,335 ,232 ,293 ,13 ,114 ,180 ,27 ,390 ,363 ,360 ,252 ,279 ,425 ,38 ,135 ,27 ,10 ,149 ,48 ,460 ,284 ,225 ,225 ,22 ,387 ,214 ,113 ,147 ,458 ,7 ,153 ,150 ,84 ,161 ,368 ,13 ,169 ,27 ,334 ,368 ,293 ,150 ,365 ,81 ,220 ,263 ,45 ,416 ,370 ,452 ,139 ,159 ,264 ,478 ,310 ,222 ,188 ,95 ,63 ,130 ,4 ,310 ,223 ,391 ,352 ,359 ,432 ,303 ,378 ,378 ,20 ,419 ,38 ,221 ,160 ,147 ,310 ,210 ,161 ,15 ,84 ,308 ,325 ,223 ,63 ,473 ,269 ,310 ,121 ,38 ,353 ,341 ,433 ,43 ,423 ,181 ,84 ,477 ,387 ,378 ,297 ,8 ,405 ,310 ,500 ,494 ,457 ,66 ,276 }
{1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 ,19 ,20 ,21 ,22 ,23 ,24 ,25 ,26 ,27 ,28 ,29 ,30 ,31 ,32 ,33 ,35 ,36 ,37 ,38 ,39 ,40 ,41 ,42 ,43 ,44 ,45 ,46 ,47 ,48 ,49 ,50 ,51 ,52 ,53 ,54 ,55 ,56 ,57 ,58 ,59 ,60 ,61 ,62 ,63 ,64 ,65 ,66 ,67 ,68 ,69 ,70 ,71 ,72 ,73 ,74 ,75 ,76 ,77 ,78 ,79 ,80 ,81 ,82 ,83 ,84 ,85 ,86 ,87 ,88 ,89 ,90 ,91 ,92 ,93 ,94 ,95 ,96 ,97 ,98 ,99 ,100 ,101 ,102 ,103 ,104 ,105 ,106 ,107 ,108 ,109 ,110 ,111 ,112 ,113 ,114 ,115 ,116 ,117 ,118 ,119 ,120 ,121 ,122 ,123 ,124 ,125 ,126 ,127 ,128 ,129 ,130 ,131 ,132 ,133 ,134 ,135 ,136 ,137 ,138 ,139 ,140 ,141 ,142 ,143 ,144 ,145 ,146 ,147 ,148 ,149 ,150 ,151 ,152 ,153 ,154 ,155 ,156 ,157 ,158 ,159 ,160 ,161 ,162 ,163 ,164 ,165 ,166 ,167 ,168 ,169 ,170 ,171 ,172 ,173 ,174 ,175 ,176 ,177 ,178 ,179 ,180 ,181 ,182 ,183 ,184 ,185 ,186 ,187 ,188 ,189 ,190 ,191 ,192 ,193 ,194 ,195 ,196 ,197 ,198 ,199 ,200 ,201 ,202 ,203 ,204 ,205 ,206 ,207 ,208 ,209 ,210 ,211 ,212 ,213 ,214 ,215 ,216 ,217 ,218 ,219 ,220 ,221 ,222 ,223 ,224 ,225 ,226 ,227 ,228 ,229 ,230 ,231 ,232 ,233 ,234 ,235 ,236 ,237 ,238 ,239 ,240 ,241 ,242 ,243 ,244 ,245 ,246 ,247 ,248 ,249 ,250 ,251 ,252 ,253 ,254 ,255 ,256 ,257 ,258 ,259 ,260 ,261 ,262 ,263 ,264 ,265 ,266 ,267 ,268 ,269 ,270 ,271 ,272 ,273 ,274 ,275 ,276 ,277 ,278 ,279 ,280 ,281 ,282 ,283 ,284 ,285 ,286 ,287 ,288 ,289 ,290 ,291 ,292 ,293 ,294 ,295 ,296 ,297 ,298 ,299 ,300 ,301 ,302 ,303 ,304 ,305 ,306 ,307 ,308 ,309 ,310 ,311 ,312 ,313 ,314 ,315 ,316 ,317 ,318 ,319 ,320 ,321 ,322 ,323 ,324 ,325 ,326 ,327 ,328 ,329 ,330 ,331 ,332 ,333 ,334 ,335 ,336 ,337 ,338 ,339 ,340 ,341 ,342 ,343 ,344 ,345 ,346 ,347 ,348 ,349 ,350 ,351 ,352 ,353 ,354 ,355 ,356 ,357 ,358 ,359 ,360 ,361 ,362 ,363 ,364 ,365 ,366 ,367 ,368 ,369 ,370 ,371 ,372 ,373 ,374 ,375 ,376 ,377 ,378 ,379 ,380 ,381 ,382 ,383 ,384 ,385 ,386 ,387 ,388 ,389 ,390 ,391 ,392 ,393 ,394 ,395 ,396 ,397 ,398 ,399 ,400 ,401 ,402 ,403 ,404 ,405 ,406 ,407 ,408 ,409 ,410 ,411 ,412 ,413 ,414 ,415 ,416 ,417 ,418 ,419 ,420 ,421 ,422 ,423 ,424 ,425 ,426 ,427 ,428 ,429 ,430 ,431 ,432 ,433 ,434 ,435 ,436 ,437 ,438 ,439 ,440 ,441 ,442 ,443 ,444 ,445 ,446 ,447 ,448 ,449 ,450 ,451 ,452 ,453 ,454 ,455 ,456 ,457 ,458 ,459 ,460 ,461 ,462 ,463 ,464 ,465 ,466 ,467 ,468 ,469 ,470 ,471 ,472 ,473 ,474 ,475 ,476 ,477 ,478 ,479 ,480 ,481 ,482 ,483 ,484 ,485 ,486 ,487 ,488 ,489 ,490 ,491 ,492 ,493 ,494 ,495 ,496 ,497 ,498 ,499 ,500 }
{49 ,7 ,3 ,58 ,79 ,42 ,16 ,95 ,29 ,2 ,56 ,73 ,41 ,33 ,48 ,21 ,41 ,5 ,16 ,34 ,93 ,56 ,33 ,96 ,46 ,40 ,33 ,62 ,49 ,74 ,58 ,88 ,30 ,88 ,33 ,49 ,42 ,14 ,18 ,87 ,62 ,62 ,70 ,11 ,27 ,44 ,15 ,40 ,4 ,8 ,94 ,63 ,97 ,77 ,32 ,73 ,64 ,74 ,68 ,3 ,24 ,45 ,91 ,55 ,24 ,31 ,58 ,14 ,8 ,52 ,70 ,58 ,60 ,65 ,13 ,6 ,38 ,67 ,17 ,9 ,56 ,81 ,30 ,91 ,31 ,49 ,100 ,76 ,93 ,61 ,88 ,16 ,29 ,17 ,39 ,61 ,25 ,51 ,31 ,64 ,42 ,29 ,99 ,81 ,15 ,27 ,76 ,13 ,18 ,89 ,29 ,74 ,32 ,18 ,47 ,19 ,26 ,48 ,80 ,58 ,30 ,45 ,26 ,11 ,94 ,59 ,75 ,84 ,76 ,97 ,31 ,58 ,96 ,12 ,22 ,39 ,69 ,7 ,36 ,67 ,19 ,16 ,15 ,34 ,43 ,1 ,1 ,3 ,64 ,96 ,64 ,64 ,16 ,7 ,74 ,30 ,78 ,76 ,4 ,3 ,31 ,59 ,89 ,52 ,62 ,80 ,8 ,96 ,2 ,26 ,84 ,10 ,26 ,87 ,2 ,97 ,14 ,60 ,16 ,71 ,54 ,93 ,96 ,12 ,33 ,15 ,22 ,8 ,38 ,59 ,25 ,70 ,31 ,80 ,16 ,92 ,74 ,97 ,47 ,62 ,25 ,29 ,64 ,76 ,16 ,21 ,82 ,20 ,68 ,29 ,44 ,41 ,66 ,32 ,36 ,96 ,70 ,43 ,53 ,25 ,28 ,94 ,18 ,17 ,57 ,3 ,5 ,51 ,64 ,14 ,33 ,47 ,51 ,76 ,77 ,51 ,21 ,12 ,20 ,15 ,2 ,82 ,67 ,9 ,63 ,5 ,84 ,26 ,56 ,79 ,86 ,10 ,52 ,25 ,59 ,84 ,34 ,86 ,12 ,2 ,57 ,7 ,2 ,21 ,71 ,86 ,54 ,31 ,99 ,19 ,16 ,46 ,58 ,82 ,39 ,37 ,79 ,99 ,24 ,6 ,43 ,67 ,83 ,97 ,100 ,17 ,59 ,100 ,26 ,12 ,90 ,97 ,65 ,20 ,40 ,26 ,47 ,74 ,65 ,78 ,49 ,57 ,55 ,70 ,27 ,95 ,44 ,89 ,7 ,47 ,81 ,49 ,15 ,54 ,84 ,39 ,92 ,1 ,35 ,61 ,38 ,72 ,43 ,51 ,7 ,8 ,42 ,98 ,97 ,38 ,100 ,54 ,28 ,69 ,12 ,19 ,44 ,66 ,36 ,62 ,100 ,47 ,57 ,98 ,83 ,86 ,75 ,71 ,61 ,92 ,81 ,80 ,94 ,82 ,20 ,96 ,9 ,17 ,59 ,36 ,88 ,22 ,78 ,90 ,21 ,36 ,98 ,36 ,52 ,44 ,100 ,39 ,89 ,73 ,7 ,22 ,99 ,2 ,44 ,98 ,47 ,58 ,18 ,3 ,45 ,44 ,13 ,51 ,82 ,72 ,17 ,22 ,66 ,42 ,40 ,42 ,31 ,78 ,4 ,48 ,75 ,39 ,96 ,87 ,35 ,100 ,33 ,11 ,87 ,97 ,89 ,24 ,15 ,17 ,73 ,98 ,26 ,24 ,4 ,31 ,39 ,56 ,41 ,88 ,54 ,75 ,25 ,1 ,83 ,56 ,16 ,36 ,36 ,6 ,100 ,82 ,4 ,10 ,81 ,67 ,51 ,32 ,63 ,9 ,85 ,18 ,29 ,93 ,59 ,31 ,92 ,58 ,49 ,93 ,13 ,50 ,78 ,77 ,8 ,40 ,84 ,25 ,49 ,73 ,53 ,2 ,53 ,82 ,28 ,5 ,71 ,39 ,92 ,23 ,31 ,24 ,43 ,21 ,15 ,7 ,89 ,9 ,94 ,36 ,61 ,97 ,71 ,46 ,9 ,57 ,71 ,11 ,29 ,70 ,76 ,12 ,42 ,17 ,18 }
Returns: 23939

Submissions are judged against all 20 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DismantleTheTree with a public method int dismantle(int N, vector<int> X, vector<int> Y, vector<int> weight) · 20 test cases · 2 s / 256 MB per case

Submitting as anonymous