QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#413007 | #6745. Delete the Tree | Savior | WA | 1ms | 3676kb | C++20 | 1.4kb | 2024-05-16 23:39:55 | 2024-05-16 23:39:55 |
Judging History
answer
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
#define int long long
using ll = long long;
const int inf = 1e17+7;
const int N=505;
const int mod =1e9+7;
typedef pair<int,int>P;
int mn=inf,rt=0,n=0;
int tot=0;
int sz[N];
vector<int>ans[N];
int vis[N];
vector<int>e[N];
void get(int u,int fa){
sz[u]=1;
int mx=0;
for(auto v:e[u]){
if(v==fa||vis[v]) continue;
get(v,u);
mx=max(mx,sz[v]);
sz[u]+=sz[v];
}
mx=max(mx,n-sz[u]-1);
if(mx<mn) mn=mx,rt=u;
return;
}
void dfs(int u,int fa,int w){
if(vis[u]) return;
ans[w].push_back(u);
tot=max(tot,w);
vis[u]=1;
for(auto v:e[u]){
if(v==fa||vis[v]) continue;
mn=inf,n=sz[v];
get(v,u);
get(rt,rt);
dfs(rt,0,w+1);
}
}
void solve(){
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
get(1,0);
get(rt,rt);
dfs(rt,0,1);
cout<<tot<<endl;
for(int i=tot;i>=0;i--){
cout<<ans[i].size()<<' ';
for(auto it:ans[i])
cout<<it<<' ';
cout<<endl;
}
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t=1;//cin>>t;
while(t--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3588kb
input:
5 1 2 1 3 1 4 4 5
output:
3 1 5 3 2 3 4 1 1 0
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3564kb
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: 1ms
memory: 3648kb
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 1 323 205 480 454 142 346 389 232 228 357 362 316 163 176 210 294 124 339 223 409 175 474 181 81 140 301 134 215 471 4 122 456 160 484 331 318 22 69 105 342 219 363 446 194 408 25 101 84 407 60 488 348 157 358 211 423 169 403 303 499 486 286 436 356 493 190 47 366 347 90 213 264 75 398 102 70 ...
result:
ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 3620kb
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:
10 82 413 74 147 335 350 410 382 451 133 86 213 269 482 231 490 58 365 81 359 467 212 334 270 152 346 329 280 46 76 452 14 358 202 184 125 153 66 61 185 284 114 29 469 119 158 172 491 403 177 492 311 25 108 182 88 444 495 460 117 498 307 316 131 379 323 208 399 157 303 459 224 215 225 390 244 165 14...
result:
ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 3496kb
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:
10 1 178 15 17 381 303 69 74 283 280 80 192 279 16 372 419 135 43 76 147 441 223 422 442 189 169 109 184 19 500 225 25 240 334 457 494 81 91 194 410 24 89 86 322 111 166 398 246 264 482 484 58 228 256 252 346 336 431 115 473 164 438 97 311 363 98 245 227 437 456 207 84 318 274 413 275 112 267 239 ...
result:
ok
Test #6:
score: 0
Accepted
time: 1ms
memory: 3488kb
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: 1ms
memory: 3608kb
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:
10 4 385 307 178 82 36 374 302 150 330 452 13 27 23 440 162 460 215 169 386 305 347 188 181 123 373 348 7 419 316 275 323 448 446 453 18 65 292 249 93 144 131 86 463 344 371 414 206 43 429 225 308 121 444 83 422 415 80 367 122 184 286 476 311 81 255 8 466 174 405 180 331 418 32 266 435 213 290 377...
result:
ok
Test #8:
score: 0
Accepted
time: 1ms
memory: 3588kb
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:
10 1 312 8 371 436 66 327 42 158 388 23 35 444 111 447 11 224 7 239 174 151 163 490 126 249 223 481 84 352 437 405 395 261 244 83 44 317 417 389 76 290 272 348 465 213 284 35 105 473 273 184 54 22 342 69 182 100 310 462 1 81 416 424 110 409 251 404 319 414 498 402 53 65 139 216 233 87 420 29 449 ...
result:
ok
Test #9:
score: 0
Accepted
time: 1ms
memory: 3676kb
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:
10 16 150 411 369 236 261 366 1 289 295 70 217 155 371 334 254 163 58 223 94 418 293 263 313 464 235 75 360 45 233 428 267 381 415 58 65 146 287 311 23 298 110 158 16 500 162 337 188 225 316 126 197 469 395 27 461 179 22 91 25 353 123 281 68 202 89 17 245 374 48 455 43 373 131 81 299 102 478 41 44...
result:
ok
Test #10:
score: 0
Accepted
time: 1ms
memory: 3640kb
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:
9 5 421 409 418 92 193 209 366 44 472 317 388 61 350 426 4 138 122 319 223 207 398 128 104 165 494 328 382 222 416 227 136 325 161 254 221 100 443 467 252 268 320 121 260 247 490 163 6 284 208 164 282 304 393 99 173 28 241 332 314 115 78 327 235 392 367 16 313 110 364 68 182 156 300 204 315 198 90 ...
result:
ok
Test #11:
score: 0
Accepted
time: 1ms
memory: 3496kb
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:
10 40 480 65 73 23 494 267 206 389 59 76 368 62 67 350 483 195 78 450 454 261 200 48 263 37 39 288 440 167 367 187 306 38 136 471 61 464 344 13 466 129 93 175 374 280 275 29 155 107 99 212 192 233 135 459 164 315 463 255 191 364 14 237 4 423 308 35 460 43 325 216 178 72 321 50 24 385 298 381 31 479...
result:
ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 3604kb
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 4 31 66 330 210 68 76 241 207 125 395 316 51 471 334 114 2 365 233 58 303 92 411 42 282 299 185 437 18 364 438 168 154 105 199 291 424 392 496 449 263 414 418 117 382 178 426 286 101 481 213 212 220 135 85 143 478 176 162 160 27 243 173 146 145 244 229 250 98 337 25 5 269 55 164 8 315 167 137 34...
result:
ok
Test #13:
score: 0
Accepted
time: 1ms
memory: 3624kb
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 27 23 354 203 463 230 111 76 130 412 326 164 66 284 407 172 176 14 205 466 237 194 244 221 410 99 83 445 108 157 245 240 477 16 179 22 457 439 239 382 391 461 373 323 167 110 316 321 332 292 59 488 288 45 39 153 406 78 421 180 1 498 238 427 350 453 5 304 451 367 414 379 454 102 295 120 264 222 31...
result:
ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 3548kb
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 2 196 197 43 254 119 99 399 261 152 311 277 19 354 434 30 58 105 425 11 115 127 204 323 358 7 93 338 329 428 136 25 351 393 405 61 331 272 433 38 441 321 301 381 219 455 60 118 469 245 265 31 15 174 209 300 296 150 166 133 230 161 126 97 170 292 57 240 79 435 146 456 158 308 75 382 157 376 270 4...
result:
ok
Test #15:
score: 0
Accepted
time: 1ms
memory: 3588kb
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 22 281 57 55 28 63 85 87 278 413 141 251 76 467 341 156 248 474 110 359 243 364 383 84 258 457 61 24 168 214 162 365 392 13 194 458 150 216 62 56 236 442 153 454 384 291 213 166 234 101 2 163 412 50 358 267 449 265 147 129 336 456 387 254 274 257 130 296 72 368 39 83 362 90 255 345 114 67 478 199...
result:
ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3668kb
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:
9 2 362 430 40 35 127 422 425 371 144 433 94 234 225 242 179 257 499 17 318 44 463 212 336 384 82 183 301 303 27 398 308 79 490 23 305 284 245 43 489 26 320 464 152 132 157 354 322 480 10 293 485 19 441 482 420 411 109 230 201 392 281 466 283 426 374 116 92 240 218 494 269 122 290 385 106 32 469 3...
result:
ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 3672kb
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:
10 16 188 267 458 357 367 326 19 170 28 336 341 420 201 86 58 216 46 329 391 121 370 486 404 260 152 172 150 462 421 240 444 380 480 356 159 289 140 255 70 439 214 425 271 80 305 494 97 269 193 164 182 338 18 63 67 279 437 374 246 229 498 213 9 73 315 263 288 266 410 117 157 73 286 350 378 392 109...
result:
ok
Test #18:
score: -100
Wrong Answer
time: 1ms
memory: 3548kb
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:
11 8 55 46 435 114 424 23 463 96 62 413 6 251 270 207 123 406 357 58 237 408 282 378 279 314 184 474 319 169 202 448 71 281 296 130 475 392 444 116 283 188 245 352 241 103 414 399 181 452 1 233 324 454 217 69 278 191 253 163 341 192 292 461 44 152 386 410 465 235 247 193 10 117 2 172 300 321 93 50...
result:
wrong answer Integer 11 violates the range [0, 10]