QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#413006 | #6745. Delete the Tree | Savior | WA | 1ms | 3716kb | C++20 | 1.4kb | 2024-05-16 23:38:51 | 2024-05-16 23:38:51 |
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);
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3528kb
input:
5 1 2 1 3 1 4 4 5
output:
3 2 2 3 2 1 5 1 4 0
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3716kb
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: 3592kb
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: 3516kb
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: 3668kb
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 19 219 292 9 319 271 100 171 337 376 1 27 363 178 381 303 69 74 283 280 87 134 320 288 207 96 465 338 298 141 203 449 220 245 331 132 43 266 311 343 128 448 121 10 164 144 326 369 77 408 388 270 48 243 481 293 228 441 223 422 442 189 169 109 184 19 500 225 25 240 334 457 494 81 91 194 410 24 89 8...
result:
ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3564kb
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: 3492kb
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: 3492kb
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 2 371 312 13 444 111 447 11 224 7 436 66 327 42 158 388 23 51 273 184 54 22 342 69 182 100 310 462 1 81 416 424 110 409 251 404 319 414 498 402 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 115 473 28 140 364 186 487 246 384 480 ...
result:
ok
Test #9:
score: -100
Wrong Answer
time: 1ms
memory: 3504kb
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:
11 8 19 411 369 236 261 366 1 289 37 453 150 5 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 295 70 217 155 371 334 254 163 79 479 223 170 190 143 418 49 457 98 446 308 481 136 368 156 440 416 157 348 444 410 319 499 11 327 432 483 189 82 106 62 ...
result:
wrong answer Integer 11 violates the range [0, 10]