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