QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#413006#6745. Delete the TreeSaviorWA 1ms3716kbC++201.4kb2024-05-16 23:38:512024-05-16 23:38:51

Judging History

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

  • [2024-05-16 23:38:51]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3716kb
  • [2024-05-16 23:38:51]
  • 提交

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]