QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#176418 | #6745. Delete the Tree | SnowNorth | AC ✓ | 1ms | 3928kb | C++14 | 1.8kb | 2023-09-11 16:50:56 | 2023-09-11 16:50:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
vector<int> G[N];
int siz[N], maxs[N];
bool del[N];
vector<int> G2[N];
int f[N], id[N];
void dvd(int u, int s, int fa) {
int ms = s + 1, root = -1;
function<void(int, int)> dfs1 = [&](int u, int rt) {
siz[u] = 1;
maxs[u] = 0;
for (auto v : G[u]) {
if (del[v] || v == rt) continue ;
dfs1(v, u);
siz[u] += siz[v];
maxs[u] = max(maxs[u], siz[v]);
}
maxs[u] = max(maxs[u], s - siz[u]);
if (maxs[u] < ms) ms = maxs[u], root = u;
};
dfs1(u, 0);
G2[fa].push_back(root);
for (auto v : G[root]) {
if (del[v]) continue ;
function<void(int, int)> dfs2 = [&](int u, int rt) {
siz[u] = 1;
for (auto v : G[u]) {
if (del[v] || v == rt) continue ;
dfs2(v, u);
siz[u] += siz[v];
}
};
dfs2(v, root);
}
del[root] = 1;
for (auto v : G[root]) {
if (!del[v]) dvd(v, siz[v], root);
}
}
void dfs(int u) {
if (G2[u].empty()) f[u] = 1;
for (auto v : G2[u]) {
dfs(v);
f[u] = max(f[u], f[v] + 1);
}
}
void solve() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dvd(1, n, 0);
dfs(0);
for (int i = 1; i <= n; i++) id[i] = i;
sort(id + 1, id + n + 1, [](int A, int B) {
return f[A] < f[B];
});
int ans = 1;
vector<int> vec[20];
for (int i = 1; i <= n; i++) {
if (i > 1 && f[id[i]] != f[id[i - 1]]) ++ans;
vec[ans].push_back(id[i]);
}
cout << ans << '\n';
for (int i = 1; i <= ans; i++) {
cout << vec[i].size() << ' ';
for (auto v : vec[i]) cout << v << ' ';
cout << '\n';
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3660kb
input:
5 1 2 1 3 1 4 4 5
output:
3 3 2 3 4 1 5 1 1
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3692kb
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 328 343 342 341 340 339 338 337 336 335 334 333 332 331 330 329 344 327 326 325 324 323 322 321 320 319 318 317 316 315 314 313 359 374 373 372 371 370 369 368 367 366 365 364 363 362 361 360 312 358 357 356 355 354 353 352 351 350 349 348 347 346 345 265 280 279 278 277 276 275 274 273 272 27...
result:
ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 3628kb
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 329 344 343 342 341 340 339 338 337 336 335 334 333 332 331 330 345 328 327 326 325 324 323 322 321 320 319 318 317 316 315 314 360 375 374 373 372 371 370 369 368 367 366 365 364 363 362 361 313 359 358 357 356 355 354 353 352 351 350 349 348 347 346 266 281 280 279 278 277 276 275 274 273 27...
result:
ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 3732kb
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 245 386 196 379 194 382 383 190 385 188 378 185 388 183 182 181 390 179 365 215 214 212 211 210 360 362 363 392 204 203 202 369 200 371 375 413 155 154 152 150 149 147 409 411 156 414 141 140 416 137 418 419 356 157 158 406 160 404 162 163 401 400 399 398 170 171 174 395 266 320 322 325 326 270 26...
result:
ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 3628kb
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 252 235 427 428 250 246 243 241 240 239 432 255 234 233 434 231 228 226 223 222 221 268 278 277 275 274 273 272 271 421 269 220 422 266 264 263 262 261 260 423 424 170 182 181 180 448 178 449 450 174 173 184 169 168 453 166 454 164 163 161 160 445 436 218 217 213 439 206 205 443 444 420 197 196 19...
result:
ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3696kb
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 321 340 339 338 337 334 333 332 331 330 329 328 327 326 324 322 341 320 319 318 317 316 315 314 313 312 311 310 309 308 307 356 371 370 369 368 367 366 365 364 363 362 361 360 359 358 357 306 355 354 353 352 351 350 349 348 347 346 345 344 343 342 260 275 274 273 272 271 270 269 268 267 266 26...
result:
ok
Test #7:
score: 0
Accepted
time: 1ms
memory: 3688kb
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 272 202 376 211 377 378 207 385 386 387 203 213 201 200 388 198 389 390 391 392 367 233 232 360 362 229 228 364 366 225 393 368 370 371 372 218 217 374 214 164 406 172 171 408 409 168 167 166 165 174 163 410 411 160 412 415 155 152 184 192 394 395 189 397 187 398 399 358 400 182 401 180 179 402 17...
result:
ok
Test #8:
score: 0
Accepted
time: 1ms
memory: 3692kb
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:
8 269 263 283 282 281 275 274 270 268 266 265 264 284 260 259 258 257 256 254 253 252 250 248 310 334 331 330 326 320 319 316 315 313 311 247 309 307 304 298 296 294 292 291 290 286 191 203 202 201 200 199 198 197 196 194 192 206 190 188 186 184 183 182 181 179 178 177 225 245 244 242 241 239 238 23...
result:
ok
Test #9:
score: 0
Accepted
time: 1ms
memory: 3692kb
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 325 296 314 313 312 309 307 306 305 304 303 302 301 298 315 295 294 292 291 290 289 282 281 279 276 275 331 347 346 345 343 342 341 340 339 336 334 333 332 273 330 329 328 326 325 324 322 321 318 317 316 218 238 236 233 232 231 229 227 224 222 221 220 219 239 216 215 213 212 211 210 207 206 205 20...
result:
ok
Test #10:
score: 0
Accepted
time: 1ms
memory: 3660kb
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 289 305 304 302 301 300 298 297 296 295 294 293 290 306 287 285 284 283 282 280 279 278 277 276 272 323 339 336 335 333 332 331 329 328 327 326 325 324 271 322 320 319 317 315 314 313 310 309 308 307 220 236 235 232 231 228 227 226 225 224 223 222 221 237 219 215 214 211 208 207 206 205 204 20...
result:
ok
Test #11:
score: 0
Accepted
time: 1ms
memory: 3916kb
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 247 494 293 292 286 283 282 279 274 273 270 269 294 264 260 258 254 253 246 244 243 495 305 321 320 319 317 316 313 309 308 307 306 234 304 303 302 301 300 298 297 296 295 183 201 200 199 197 497 193 191 188 186 184 203 182 179 177 174 173 172 171 169 167 220 232 231 230 228 227 226 225 222 221 32...
result:
ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 3928kb
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:
8 261 271 293 291 290 288 286 280 278 275 274 273 297 270 269 268 267 264 261 258 257 255 316 337 333 329 328 327 326 323 322 318 317 254 314 313 311 309 306 304 302 299 298 189 208 205 201 200 198 196 195 194 193 190 209 188 187 184 180 179 178 176 175 170 239 253 251 250 249 248 244 243 242 241 24...
result:
ok
Test #13:
score: 0
Accepted
time: 1ms
memory: 3696kb
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 277 241 254 253 252 439 250 249 248 247 245 440 255 239 238 237 236 443 234 233 232 231 271 290 288 287 286 426 283 429 430 277 433 229 434 436 437 264 263 262 261 438 256 452 195 448 191 449 187 186 184 451 180 179 196 177 175 174 173 172 171 170 169 168 213 227 444 225 223 222 219 218 215 214 29...
result:
ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 3688kb
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:
8 306 255 268 267 442 264 263 262 260 259 443 444 447 269 448 252 452 453 246 245 455 242 456 240 283 294 293 292 291 290 289 438 287 439 284 236 282 281 279 440 277 276 441 272 271 270 194 208 207 206 204 203 463 201 200 199 198 464 209 192 465 190 189 187 186 185 183 182 181 223 234 233 232 458 23...
result:
ok
Test #15:
score: 0
Accepted
time: 1ms
memory: 3820kb
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:
8 243 278 296 293 292 290 288 287 285 283 282 280 298 276 273 272 269 266 265 263 262 260 257 316 336 333 331 330 325 324 323 319 318 317 256 315 314 313 312 309 306 305 303 300 299 194 211 210 208 204 203 202 201 199 197 195 213 191 190 189 188 187 184 183 182 181 177 230 250 249 245 244 243 240 23...
result:
ok
Test #16:
score: 0
Accepted
time: 1ms
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:
8 239 184 193 191 190 475 188 354 186 185 352 355 356 181 357 358 178 476 176 350 348 347 474 200 201 203 345 205 206 207 344 210 211 454 140 373 374 148 376 144 380 450 141 152 139 138 137 136 135 134 133 341 153 370 158 159 160 479 163 164 366 167 365 170 171 363 477 264 272 305 270 269 268 466 30...
result:
ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 3720kb
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 355 272 288 287 455 284 283 282 281 280 278 276 275 273 289 271 270 269 456 457 264 263 262 261 260 259 301 314 313 312 311 309 308 307 305 451 303 302 257 300 452 298 297 453 295 294 454 292 291 290 206 226 221 220 219 218 215 464 212 211 210 208 227 205 204 203 202 201 200 199 198 197 196 195 24...
result:
ok
Test #18:
score: 0
Accepted
time: 1ms
memory: 3676kb
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 242 255 274 272 270 268 267 266 265 262 258 256 277 253 251 249 248 246 245 244 242 239 302 325 324 321 320 314 313 311 306 305 236 300 292 290 287 286 283 280 279 278 184 195 194 193 192 191 190 188 187 185 196 183 182 179 177 176 175 171 170 169 216 235 232 229 228 225 224 223 222 218 328 214 21...
result:
ok
Test #19:
score: 0
Accepted
time: 1ms
memory: 3684kb
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 176 165 146 150 151 153 356 355 354 353 159 349 348 347 144 345 343 169 170 171 338 176 336 179 180 182 332 388 107 108 402 400 113 114 116 117 118 119 391 389 331 123 124 385 384 131 133 379 136 371 141 366 143 274 294 293 227 290 289 286 285 279 276 236 237 275 298 273 242 271 270 266 264 248 26...
result:
ok
Test #20:
score: 0
Accepted
time: 1ms
memory: 3632kb
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 328 343 342 341 340 339 338 337 336 335 334 333 332 331 330 329 344 327 326 325 322 321 320 319 318 317 316 315 314 313 312 359 374 373 372 371 370 369 368 367 366 365 364 363 362 361 360 311 358 357 356 355 354 353 352 351 350 349 348 347 346 345 263 278 277 276 275 274 273 272 271 270 269 26...
result:
ok
Test #21:
score: 0
Accepted
time: 1ms
memory: 3696kb
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 295 286 305 301 299 297 295 292 291 290 289 288 287 306 284 283 282 280 276 275 274 273 271 269 268 320 338 337 336 335 334 331 328 327 325 323 322 266 319 317 316 315 314 312 310 309 308 307 207 232 231 229 228 224 222 218 214 213 211 209 233 203 201 199 197 196 195 192 190 189 188 246 264 263 26...
result:
ok
Test #22:
score: 0
Accepted
time: 1ms
memory: 3920kb
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 294 393 223 387 221 220 388 218 217 390 392 224 395 396 209 398 207 205 204 203 202 381 374 375 241 379 239 238 237 380 235 400 233 382 231 230 384 385 386 226 225 169 178 177 410 175 174 173 172 411 170 179 167 166 412 164 413 414 416 159 158 190 200 401 198 402 196 403 193 192 191 371 189 188 18...
result:
ok
Test #23:
score: 0
Accepted
time: 1ms
memory: 3584kb
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 264 282 281 280 278 276 274 273 271 268 267 283 263 261 259 258 255 254 253 252 250 249 302 320 316 315 314 312 311 308 307 306 305 248 300 299 297 296 293 292 289 288 286 188 206 204 197 196 194 193 192 191 190 189 207 187 185 184 183 181 180 179 178 177 174 232 247 246 245 244 243 242 241 23...
result:
ok
Test #24:
score: 0
Accepted
time: 1ms
memory: 3580kb
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 231 241 240 399 400 401 236 402 234 233 232 242 230 229 228 227 226 225 224 223 221 220 393 263 262 390 391 259 392 257 256 255 254 219 252 251 250 249 394 247 395 397 244 243 413 412 196 195 194 193 192 191 190 189 188 410 186 185 414 183 181 180 416 178 417 175 208 218 217 216 215 214 213 21...
result:
ok