QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#413007#6745. Delete the TreeSaviorWA 1ms3676kbC++201.4kb2024-05-16 23:39:552024-05-16 23:39:55

Judging History

你现在查看的是最新测评结果

  • [2024-05-16 23:39:55]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3676kb
  • [2024-05-16 23:39:55]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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]