QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#186227 | #6745. Delete the Tree | UrgantTeam# | WA | 1ms | 3696kb | C++23 | 1.6kb | 2023-09-23 13:54:00 | 2023-09-23 13:54:02 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long double ld;
typedef long long ll;
vector <int> g[505];
vector <pair <int, int> > vert;
vector <int> indep[15];
bool dead[505];
void dfs(int v, int pr, int h)
{
vert.pb(mp(h, v));
for (int u : g[v])
if (u != pr) dfs(u, v, h + 1);
return;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].pb(v), g[v].pb(u);
}
int ans_op = 0;
while (ans_op < 10)
{
ans_op++;
int root = 0;
for (int i = 1; i <= n; i++)
if (!dead[i]) {root = i; break;}
if (root == 0)
{
ans_op--;
break;
}
vert.clear();
dfs(root, 0, 0);
sort(vert.begin(), vert.end());
for (int i = (int) vert.size() - 1; i >= 0; i--)
{
int v = vert[i].y;
bool fl = true;
for (int u : g[v])
if (dead[u]) fl = false;
if (fl && (int) g[v].size() <= 2) dead[v] = true, indep[ans_op].pb(v);
}
for (int v : indep[ans_op])
{
for (int u : g[v])
g[u].erase(find(g[u].begin(), g[u].end(), v));
if ((int) g[v].size() == 2)
{
int a = g[v][0], b = g[v][1];
g[a].pb(b), g[b].pb(a);
}
}
}
cout << ans_op << '\n';
for (int i = 1; i <= ans_op; i++)
{
cout << indep[i].size() << ' ';
for (int v : indep[i]) cout << v << ' ';
cout << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3656kb
input:
5 1 2 1 3 1 4 4 5
output:
3 3 5 3 2 1 4 1 1
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3668kb
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 500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 427 42...
result:
ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 3668kb
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 500 498 494 492 490 489 487 483 482 478 472 465 463 461 459 458 457 455 453 451 447 444 443 442 441 440 439 438 437 435 434 433 431 430 428 426 424 422 419 417 416 415 414 413 411 410 406 404 402 401 400 399 396 395 393 392 391 390 386 384 383 382 381 380 378 377 375 374 373 370 367 364 361 36...
result:
ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 3696kb
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 250 387 301 13 176 74 415 448 285 264 314 54 484 350 164 8 230 408 410 318 328 494 111 21 477 273 133 310 78 480 192 417 471 266 432 424 269 12 308 226 333 234 104 70 434 457 406 179 473 239 227 190 365 79 81 123 416 483 80 338 467 5 470 22 188 212 347 476 332 341 55 270 253 152 362 371 404 89 47 ...
result:
ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 3652kb
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 251 497 493 492 483 478 474 472 471 470 469 467 463 462 460 454 445 439 432 428 427 421 420 418 412 404 403 402 401 392 391 386 383 380 378 375 374 370 368 365 362 361 360 357 356 355 354 344 341 340 333 329 325 323 318 315 313 312 307 304 302 297 285 284 282 278 277 275 274 273 272 263 262 260 25...
result:
ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3620kb
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 500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 476 475 473 472 471 470 469 468 467 466 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 448 447 446 445 444 442 441 440 439 438 437 436 435 434 433 430 429 428 426 425 424 423 422 421 420 41...
result:
ok
Test #7:
score: 0
Accepted
time: 1ms
memory: 3652kb
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 274 288 192 53 41 425 244 166 156 138 12 481 410 350 336 487 328 272 198 140 136 130 362 322 296 152 101 447 417 60 47 17 421 253 201 160 141 50 383 498 409 324 195 497 484 420 260 205 66 44 490 459 370 351 84 465 439 426 388 355 293 278 89 376 316 275 229 94 90 494 412 392 249 237 143 113 264 248...
result:
ok
Test #8:
score: 0
Accepted
time: 1ms
memory: 3688kb
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:
9 281 296 335 199 47 12 255 181 106 479 418 377 338 315 298 290 268 263 258 257 245 243 213 152 150 148 40 30 483 469 468 428 360 331 276 272 256 254 203 166 121 85 4 466 456 455 446 433 427 349 238 197 131 116 27 279 266 188 76 49 489 477 439 423 361 346 345 284 201 173 38 21 2 396 366 363 356 330 ...
result:
ok
Test #9:
score: 0
Accepted
time: 1ms
memory: 3688kb
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 349 53 270 299 121 434 81 412 71 498 92 137 87 43 119 452 455 494 48 397 374 151 245 192 161 17 335 52 288 297 202 283 371 226 396 10 172 330 390 123 386 353 271 176 25 280 357 34 108 22 310 217 194 377 214 320 74 441 9 402 72 400 433 456 70 274 126 66 230 228 79 225 234 96 188 203 497 496 493 492...
result:
ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3652kb
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 485 480 479 473 469 451 447 434 433 420 417 415 408 390 379 373 371 362 348 345 329 326 310 296 295 294 283 279 270 261 257 256 238 237 219 215 214 211 206 205 202 197 196 189 179 178 177 175 174 170 169 168 152 142 141 134 127 123 120 119 117 109 108 107 103 91 82 80 76 67 64 60 55 50 48 38 2...
result:
ok
Test #11:
score: 0
Accepted
time: 1ms
memory: 3660kb
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 251 96 394 224 491 466 351 185 207 299 13 339 318 326 449 11 19 412 82 18 61 309 471 359 109 270 230 244 38 441 92 312 486 306 323 106 498 183 324 367 357 167 430 319 440 10 328 277 194 288 158 268 420 219 119 314 105 263 44 451 467 168 98 429 95 375 261 247 149 256 472 68 384 272 78 442 249 80 39...
result:
ok
Test #12:
score: -100
Wrong Answer
time: 1ms
memory: 3672kb
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:
10 213 439 492 348 226 192 149 140 101 97 70 458 457 417 408 380 363 360 357 317 312 297 296 216 186 183 173 159 153 142 131 130 107 85 75 54 24 22 7 500 488 485 484 477 451 428 420 412 406 398 372 355 354 344 341 331 329 278 267 249 238 197 182 156 152 108 104 98 95 89 79 74 72 41 5 466 461 423 403...
result:
wrong answer