QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#186330 | #6745. Delete the Tree | UrgantTeam# | AC ✓ | 1ms | 3752kb | C++23 | 1.5kb | 2023-09-23 17:14:06 | 2023-09-23 17:14:06 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long double ld;
typedef long long ll;
vector <int> g[505];
int sz[505];
vector <int> answer[15];
void dfsik(int v, int pr)
{
sz[v] = 1;
for (int u : g[v])
if (u != pr)
{
dfsik(u, v);
sz[v] += sz[u];
}
auto pos = find(g[v].begin(), g[v].end(), pr);
if (pos != g[v].end()) g[v].erase(pos);
return;
}
void centroid(int v, int height)
{
int pos = -1;
for (int i = 0; i < (int) g[v].size(); i++)
{
int u = g[v][i];
if (2 * sz[u] > sz[v]) pos = i;
}
if (pos == -1)
{
answer[height].pb(v);
for (int u : g[v]) centroid(u, height + 1);
return;
}
int u = g[v][pos];
sz[v] -= sz[u];
sz[u] += sz[v];
g[v].erase(find(g[v].begin(), g[v].end(), u));
g[u].pb(v);
centroid(u, height);
return;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
g[a].pb(b), g[b].pb(a);
}
dfsik(1, -1);
centroid(1, 0);
int num = 0;
while (!answer[num].empty()) num++;
cout << num << '\n';
for (int i = num - 1; i >= 0; i--)
{
cout << answer[i].size() << ' ';
for (int v : answer[i]) cout << v << ' ';
cout << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3660kb
input:
5 1 2 1 3 1 4 4 5
output:
3 1 5 3 2 3 4 1 1
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
500 183 443 32 443 334 443 254 443 331 443 348 443 54 443 430 443 275 443 410 443 360 443 443 468 140 443 179 443 93 443 327 443 128 443 365 443 122 443 43 443 46 443 399 443 398 443 269 443 130 443 227 443 412 443 61 443 295 443 98 443 30 443 197 443 397 443 95 443 192 443 266 443 48 443 310 443 28...
output:
2 499 183 32 334 254 331 348 54 430 275 410 360 468 140 179 93 327 128 365 122 43 46 399 398 269 130 227 412 61 295 98 30 197 397 95 192 266 48 310 283 127 123 7 154 317 302 158 65 218 306 191 309 210 20 190 204 484 182 429 362 99 92 347 39 488 58 115 228 8 346 111 386 498 408 259 289 333 256 352 26...
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
500 80 180 80 254 1 180 80 337 180 323 80 248 180 205 80 189 180 480 80 330 180 454 80 498 142 180 80 193 180 346 80 89 180 389 80 125 180 232 80 93 180 228 80 327 180 357 80 417 180 362 80 278 180 316 80 312 163 180 80 310 176 180 80 463 180 210 80 478 180 294 80 185 124 180 80 143 180 339 80 253 1...
output:
3 249 254 337 248 189 330 498 193 89 125 93 327 417 278 312 310 463 478 185 143 253 272 277 91 404 53 68 64 424 78 458 72 5 177 156 218 48 433 137 256 245 329 333 146 131 391 94 237 413 406 65 431 441 233 377 168 118 242 298 259 285 35 63 336 344 260 483 494 465 428 386 313 186 109 414 79 191 440 34...
result:
ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
500 387 488 301 488 301 413 13 413 13 265 176 265 176 398 74 398 74 241 241 415 386 415 386 448 210 448 210 285 147 285 147 264 19 264 19 314 314 335 54 335 54 261 261 484 425 484 350 425 156 350 156 164 164 420 8 420 8 309 230 309 230 441 408 441 183 408 183 410 204 410 204 318 151 318 151 328 328 ...
output:
9 245 387 301 176 13 285 448 74 415 230 8 350 164 264 314 484 54 293 20 86 110 149 10 115 218 408 410 328 318 27 451 494 22 470 467 5 416 483 338 80 473 239 190 227 123 81 365 79 95 213 32 206 482 396 447 168 179 406 434 457 98 231 70 187 6 181 114 105 113 242 378 409 228 336 214 185 438 291 61 436 ...
result:
ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
500 147 209 104 147 13 209 209 466 104 485 17 104 13 214 13 179 151 466 176 466 130 485 286 485 17 359 17 178 214 486 55 214 179 350 179 327 151 167 151 498 146 176 102 176 99 130 130 232 286 294 286 389 56 359 330 359 178 488 178 441 440 486 210 486 55 157 55 458 237 350 350 352 327 371 317 327 167...
output:
9 1 85 252 497 262 297 341 357 356 234 113 471 263 427 260 278 362 370 304 3 5 463 313 391 73 418 472 361 41 282 374 142 90 404 392 333 412 315 44 401 325 355 250 67 107 318 274 66 478 275 112 170 196 277 33 375 272 51 32 383 123 239 197 187 420 233 307 402 439 168 329 181 205 344 445 139 403 365 2...
result:
ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
500 323 449 449 474 198 449 431 449 69 449 336 449 402 449 240 449 43 449 82 449 335 449 86 449 427 449 220 449 26 449 449 477 449 465 73 449 325 449 1 449 144 449 432 449 203 449 443 449 95 323 323 437 323 337 152 323 185 323 323 484 165 323 41 323 322 323 323 334 32 323 118 323 232 323 57 323 323 ...
output:
3 475 95 437 337 152 185 484 165 41 322 334 32 118 232 57 329 89 482 54 461 433 226 183 229 102 468 253 328 115 452 470 210 90 403 55 123 206 251 236 98 290 471 301 22 167 124 179 310 79 205 492 245 113 276 38 241 33 46 488 312 169 345 466 122 129 272 161 143 282 379 462 293 263 63 224 493 318 99 36...
result:
ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
500 274 432 133 274 274 491 274 455 207 274 274 315 265 274 10 274 203 274 274 289 274 474 374 432 414 432 116 274 385 414 274 364 1 491 10 365 432 493 10 306 374 463 5 116 302 385 265 285 127 315 86 127 127 246 282 374 98 302 98 206 282 344 127 391 127 231 62 231 33 231 86 104 211 365 194 206 194 4...
output:
9 14 180 8 466 311 81 64 430 167 150 206 414 344 27 276 92 41 166 399 47 450 152 138 487 322 253 195 392 388 497 439 94 278 412 316 319 45 2 53 288 192 481 296 447 409 383 66 420 457 260 426 465 408 205 44 21 456 372 42 151 477 416 126 325 37 352 193 100 424 223 261 405 38 418 79 32 437 284 286 317...
result:
ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
500 50 287 287 496 64 287 287 454 149 287 63 287 287 372 108 287 52 287 287 320 287 406 155 287 287 294 128 287 17 287 259 287 6 287 54 294 128 462 247 287 161 287 128 440 172 287 171 287 156 287 397 496 108 270 350 397 287 432 7 259 54 183 280 320 473 496 50 88 432 494 54 195 79 287 50 94 41 320 70...
output:
8 41 142 305 347 143 335 338 296 12 418 213 255 47 40 162 27 131 201 38 264 199 106 272 332 417 370 76 356 295 89 206 274 261 327 419 431 145 57 481 84 251 424 105 483 245 150 489 345 209 449 112 29 87 139 216 233 65 239 282 163 309 92 344 174 452 238 49 456 478 377 30 258 479 56 74 476 86 169 148 ...
result:
ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
500 93 209 209 367 209 438 209 314 209 332 152 209 209 443 209 471 209 315 209 342 209 459 209 460 209 462 209 211 209 341 191 209 209 329 185 209 209 350 209 468 209 493 209 363 209 224 35 209 209 253 209 212 86 209 204 209 186 209 209 262 193 209 209 275 209 427 141 209 88 209 149 209 209 409 209 ...
output:
9 48 53 434 3 397 452 373 390 396 439 374 161 218 83 234 244 9 433 474 123 176 252 441 377 95 168 277 378 336 323 16 375 266 392 23 6 260 174 181 296 177 113 291 381 319 104 304 200 321 128 20 485 403 447 498 71 81 412 21 77 165 490 137 87 119 43 284 7 80 281 202 283 226 371 178 257 12 238 288 52 1...
result:
ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
500 130 139 139 400 130 318 267 318 318 389 21 400 21 36 21 26 267 321 321 401 18 321 200 389 200 307 66 200 36 274 95 274 96 274 26 357 192 357 220 357 385 401 290 385 46 385 18 53 53 301 53 231 166 307 166 287 3 166 66 212 212 410 212 438 95 155 151 155 155 305 41 96 41 478 41 148 112 192 112 137 ...
output:
8 192 310 238 297 60 123 25 22 283 118 141 178 226 170 103 35 362 295 293 142 169 162 257 10 8 168 434 240 417 215 201 420 279 454 134 206 2 55 390 13 373 109 154 237 270 488 67 256 94 479 296 264 108 76 331 179 38 452 326 174 470 205 80 450 348 371 435 345 451 245 48 50 255 480 91 394 261 473 308 1...
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
500 117 264 117 456 175 264 264 500 2 456 218 456 175 480 175 343 265 500 432 500 2 475 2 487 63 218 218 421 377 480 444 480 84 343 151 343 265 281 133 265 252 432 181 432 346 475 445 475 16 487 330 487 25 63 63 102 79 421 101 421 266 377 142 377 409 444 434 444 84 291 84 284 8 151 151 333 281 358 2...
output:
9 119 96 394 491 224 207 185 466 351 410 458 344 85 299 13 296 312 92 38 441 109 270 244 230 361 464 33 354 359 471 446 489 279 188 48 435 174 403 345 277 194 158 288 37 413 268 486 306 106 323 87 240 498 328 10 319 440 202 198 430 176 463 255 15 287 97 73 439 148 308 300 423 14 237 4 113 128 116 36...
result:
ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
500 33 453 291 377 33 291 73 424 215 392 66 496 66 215 309 424 66 309 246 291 246 309 154 467 454 482 110 184 110 454 154 455 110 455 56 199 155 494 56 155 294 311 102 109 105 225 105 109 289 311 105 289 155 452 289 452 347 455 347 452 113 246 113 347 43 463 232 292 83 386 83 232 299 463 83 299 293 ...
output:
8 52 142 238 458 439 101 140 130 325 492 85 331 297 344 37 355 348 173 363 354 245 408 98 254 5 423 120 472 409 219 6 334 57 352 174 93 303 78 359 368 163 292 484 18 148 338 259 102 199 453 392 73 309 184 317 197 24 97 360 45 72 485 345 451 457 267 218 332 16 117 124 7 226 54 435 156 398 161 70 22 ...
result:
ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
500 206 498 238 388 130 427 130 388 473 498 130 473 343 352 362 421 343 421 76 170 3 180 162 460 162 180 1 76 1 162 193 421 1 193 350 473 193 350 223 488 24 30 30 223 82 300 303 468 59 125 59 468 68 82 59 68 30 107 68 107 334 406 153 278 217 372 153 217 111 334 111 217 41 190 63 288 190 288 48 230 1...
output:
8 12 397 9 32 430 441 481 432 195 376 332 278 238 120 34 304 344 84 260 369 454 337 383 74 120 222 191 264 305 146 325 256 420 147 284 97 46 442 52 404 200 186 390 437 253 184 189 175 60 129 202 94 166 61 486 469 234 71 272 464 492 28 257 225 333 154 479 314 496 418 67 136 363 485 244 108 415 148 4...
result:
ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
500 27 364 192 250 277 488 250 277 27 78 78 277 309 500 361 376 376 500 311 491 270 273 289 496 270 496 311 418 418 496 107 376 107 418 78 187 107 187 146 320 92 241 241 320 137 450 357 478 37 435 357 435 137 247 247 435 241 443 247 443 382 387 75 398 116 465 75 116 152 387 116 152 50 437 22 456 50 ...
output:
8 30 213 240 398 192 385 392 127 431 39 295 486 338 48 87 237 304 139 349 274 72 61 203 280 154 68 321 448 219 452 232 132 4 265 317 216 20 460 300 353 195 149 166 230 211 133 214 5 401 170 9 57 399 420 478 146 437 184 378 308 382 465 75 309 273 491 418 364 488 250 380 187 113 414 473 494 359 284 2...
result:
ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
500 224 468 4 105 342 365 105 365 133 224 133 365 293 476 176 389 389 476 162 227 41 411 453 489 411 453 36 162 36 453 297 389 36 297 133 485 297 485 23 486 95 136 136 486 158 314 10 65 302 491 65 491 314 495 491 495 54 136 54 495 169 488 91 483 40 68 40 483 214 488 40 214 186 375 372 465 186 465 59...
output:
8 91 192 44 91 4 335 88 463 32 9 393 364 69 118 261 110 310 81 111 437 17 151 12 172 121 298 408 128 341 229 474 86 237 464 377 248 470 185 371 55 33 83 73 39 484 191 123 87 63 198 250 462 146 6 131 428 252 251 354 263 230 199 278 286 322 480 165 433 466 424 442 15 20 253 223 166 115 157 138 179 268...
result:
ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
500 289 469 30 302 94 224 94 302 175 469 94 175 363 495 38 385 385 495 211 433 106 239 202 268 106 202 32 433 32 202 114 385 32 114 175 455 114 455 92 216 14 459 216 459 262 299 63 321 116 228 63 116 111 299 111 116 324 459 111 324 122 165 269 274 15 193 15 269 144 165 15 144 65 360 77 240 240 360 2...
output:
8 19 204 426 274 30 215 191 421 450 349 49 451 406 133 314 25 26 460 37 245 152 103 322 105 445 337 164 19 443 169 136 420 109 335 411 135 364 345 281 332 283 425 195 321 92 65 410 20 494 122 193 269 363 239 211 32 289 224 302 256 455 186 387 265 456 368 312 21 248 263 264 355 300 93 241 491 353 20...
result:
ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
500 139 315 285 315 263 285 263 329 329 335 132 335 132 288 231 288 231 391 266 391 266 430 410 430 307 410 307 379 117 379 117 121 121 441 370 441 188 370 157 188 157 200 200 486 73 486 73 267 267 404 32 404 32 260 260 286 286 296 296 499 350 499 173 350 152 173 152 458 378 458 114 378 114 172 172 ...
output:
9 48 139 285 132 329 307 430 231 441 188 486 286 267 408 345 383 152 172 109 357 147 265 248 70 380 52 500 55 274 23 258 268 259 235 186 341 306 77 354 58 333 375 225 113 164 446 45 293 230 87 315 335 410 391 370 200 260 404 256 111 421 137 444 240 458 114 462 150 244 484 187 28 349 141 310 245 72 ...
result:
ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
500 315 328 140 315 140 285 2 285 2 455 381 455 381 391 244 391 172 244 101 172 101 479 7 479 7 456 456 478 372 478 300 372 300 471 321 471 321 413 182 413 182 209 93 209 93 359 6 359 6 500 418 500 276 418 251 276 251 291 291 388 388 400 288 400 277 288 123 277 81 123 81 165 164 165 99 164 99 406 15...
output:
9 147 328 140 381 2 456 479 244 26 72 294 389 404 376 67 54 360 318 31 207 299 433 495 442 471 413 93 251 6 16 379 492 474 39 366 240 289 342 385 354 38 80 311 46 416 357 286 58 277 164 312 406 120 12 19 70 243 298 414 104 24 369 187 186 118 158 114 462 444 301 116 36 60 166 303 71 371 86 323 394 13...
result:
ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
500 87 420 87 165 165 457 85 457 85 187 187 435 56 435 56 409 268 409 153 268 40 153 40 225 225 451 68 451 68 362 88 362 88 190 190 397 122 397 122 264 202 264 75 202 304 420 304 319 200 319 200 258 258 318 24 318 24 138 78 138 78 357 209 357 209 497 58 497 16 58 16 196 196 488 124 488 124 155 155 4...
output:
6 169 75 397 225 88 87 187 153 462 130 16 155 304 318 497 138 325 238 351 223 125 184 310 185 173 15 168 438 112 11 110 19 476 320 382 374 399 212 60 330 250 272 428 241 442 206 33 352 192 232 25 471 334 296 444 104 468 93 55 90 157 219 53 359 103 423 301 396 463 86 6 441 128 254 154 135 387 411 74 ...
result:
ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
500 294 400 232 294 294 420 66 294 294 320 294 468 24 294 119 294 294 368 294 442 68 294 262 294 229 294 294 318 50 294 294 463 122 294 53 294 92 294 294 348 180 294 294 496 353 496 488 496 45 496 46 496 35 496 308 496 219 496 377 496 277 496 15 496 16 496 381 496 217 496 372 496 302 496 31 496 117 ...
output:
6 148 400 232 420 66 320 468 24 119 368 442 68 262 229 318 50 463 122 53 92 348 180 132 237 371 121 429 2 424 364 451 28 355 188 438 57 14 485 54 328 96 384 162 426 131 287 369 88 462 190 136 72 107 479 393 341 464 124 301 417 61 65 52 56 240 48 258 412 247 204 433 239 478 63 354 403 453 430 314 428...
result:
ok
Test #21:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
500 145 194 145 452 145 474 145 413 149 452 194 221 145 438 193 452 221 268 85 145 145 456 145 403 432 456 438 478 298 474 115 298 149 326 79 194 112 145 156 403 403 422 115 347 221 388 145 401 435 478 67 298 39 156 39 253 433 435 115 324 85 256 309 433 281 401 193 445 67 494 1 324 324 473 132 145 1...
output:
8 3 247 412 56 24 18 124 358 57 90 77 167 418 305 88 50 379 123 203 242 119 177 317 125 191 235 172 474 23 85 43 378 38 497 423 265 36 402 208 364 397 30 483 204 312 365 421 463 178 472 200 183 106 189 495 126 313 450 84 306 383 476 478 174 466 470 457 91 249 434 477 257 362 431 104 111 192 304 15...
result:
ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
500 206 289 289 478 239 289 212 289 212 326 173 206 262 289 24 262 239 250 289 456 326 465 35 478 465 491 215 289 124 215 215 288 8 288 157 289 289 342 116 326 326 453 206 422 236 465 116 292 325 465 2 124 326 448 188 448 132 326 69 478 133 239 8 42 24 127 28 116 135 342 262 473 115 325 126 206 268 ...
output:
8 3 171 401 337 49 469 280 390 416 225 270 252 151 380 417 359 19 58 282 400 254 305 412 57 430 366 266 65 474 278 272 398 381 311 336 274 176 227 94 490 27 314 331 79 125 33 472 198 39 257 475 358 147 1 108 104 76 476 457 399 133 264 285 310 284 172 392 261 370 435 495 220 222 123 142 410 334 379...
result:
ok
Test #23:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
500 11 250 11 273 11 192 192 360 192 426 34 426 204 426 161 204 204 413 24 413 359 413 290 359 359 386 335 386 386 422 101 422 108 422 108 171 108 183 183 304 183 313 313 497 119 313 119 202 119 370 311 370 306 370 260 306 61 306 61 439 61 110 110 367 110 256 237 256 159 256 159 208 62 159 62 177 62...
output:
9 122 360 290 161 260 202 101 304 436 285 63 340 367 208 85 325 214 43 424 190 405 283 259 357 4 408 345 84 489 156 488 268 97 134 2 145 242 71 351 342 252 276 420 289 499 400 217 317 125 321 459 269 15 301 199 253 352 406 416 380 58 314 239 407 20 120 133 418 213 68 100 435 235 425 385 494 176 194 ...
result:
ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
500 365 463 365 477 324 477 310 477 106 477 106 232 41 106 106 125 125 464 125 293 125 467 467 478 190 467 6 467 6 141 6 453 6 435 412 435 435 444 435 484 476 484 77 484 421 484 156 421 360 421 182 421 182 273 182 471 182 315 115 315 56 315 179 315 179 320 179 328 179 499 242 499 390 499 436 499 201...
output:
9 79 463 478 190 273 471 340 119 320 328 215 122 13 143 149 371 339 289 395 244 353 216 316 393 307 27 495 426 419 276 9 427 472 496 75 450 171 59 189 375 368 418 108 210 267 366 206 129 160 84 351 175 254 225 25 317 342 85 431 469 354 109 449 473 382 191 224 414 86 81 454 255 36 362 45 22 448 252 4...
result:
ok