QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#376382 | #2524. Dessert Café | FOY# | AC ✓ | 83ms | 21580kb | C++17 | 1.5kb | 2024-04-04 09:05:31 | 2024-04-04 09:05:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, k;
vector<vector<ll>> adj;
vector<bool> apt, subtree, ans;
void dfs(ll node, ll parent) {
if (apt[node]) subtree[node] = true;
for (ll child : adj[node]) {
if (child == parent) continue;
dfs(child, node);
if (subtree[child]) {
subtree[node] = true;
}
}
}
void solve(ll node, ll parent, bool flag) {
vector<ll> good;
for (ll child : adj[node]) {
if (child == parent) continue;
if (subtree[child]) good.push_back(child);
}
if (good.size() > 1) ans[node] = true;
else if (good.size() == 1 && flag) ans[node] = true;
else if (apt[node]) ans[node] = true;
for (ll child : adj[node]) {
if (child == parent) continue;
bool child_flag = flag;
if (good.size() > 1) child_flag = true;
else if (good.size() == 1 && good[0] != child) child_flag = true;
else if (apt[node]) child_flag = true;
solve(child, node, child_flag);
}
}
signed main() {
cin >> n >> k;
adj.resize(n);
apt.resize(n);
subtree.resize(n);
ans.resize(n);
ll u, v, w;
for (ll i = 0; i < n - 1; i++) {
cin >> u >> v >> w;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
ll a;
for (ll i = 0; i < k; i++) {
cin >> a;
a--;
apt[a] = true;
}
dfs(0, -1);
solve(0, -1, false);
ll cnt = 0;
for (ll i = 0; i < n; i++) {
if (ans[i]) {
cnt++;
// cout << i + 1 << " ";
}
}
cout << cnt << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3536kb
input:
9 2 1 2 8 2 4 7 4 3 6 4 6 4 5 6 3 6 7 2 6 9 5 9 8 6 1 8
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 56ms
memory: 19020kb
input:
100000 100 41922 34014 139 34014 84836 956 84836 7781 847 7781 16771 721 16771 92902 843 92902 81424 720 81424 83534 533 83534 35753 700 35753 83842 942 83842 24433 927 24433 10546 126 10546 77395 256 77395 43977 409 43977 53104 888 53104 25245 895 25245 23079 161 23079 95499 64 95499 73702 309 7370...
output:
98605
result:
ok single line: '98605'
Test #3:
score: 0
Accepted
time: 83ms
memory: 21580kb
input:
100000 50000 94951 20623 136 20623 86149 475 86149 27364 745 27364 17265 605 17265 33632 110 33632 14073 207 14073 53697 5 53697 49015 30 49015 35727 469 35727 45004 949 45004 49608 812 49608 73211 160 73211 83010 767 83010 90180 731 90180 27419 363 27419 85567 327 85567 2670 383 2670 62387 399 6238...
output:
99999
result:
ok single line: '99999'
Test #4:
score: 0
Accepted
time: 40ms
memory: 9560kb
input:
100000 55 1 2 87 1 3 60 1 4 97 1 5 28 1 6 10 1 7 36 1 8 6 1 9 59 1 10 51 1 11 69 1 12 83 1 13 91 1 14 41 1 15 47 1 16 65 1 17 93 1 18 56 1 19 51 1 20 43 1 21 74 1 22 8 1 23 50 1 24 64 1 25 34 1 26 83 1 27 48 1 28 13 1 29 10 1 30 57 1 31 62 1 32 7 1 33 82 1 34 85 1 35 84 1 36 3 1 37 23 1 38 81 1 39 3...
output:
56
result:
ok single line: '56'
Test #5:
score: 0
Accepted
time: 48ms
memory: 10288kb
input:
100000 49999 1 2 11 1 3 49 1 4 78 1 5 74 1 6 34 1 7 93 1 8 46 1 9 22 1 10 47 1 11 47 1 12 24 1 13 86 1 14 72 1 15 87 1 16 76 1 17 45 1 18 28 1 19 86 1 20 75 1 21 46 1 22 72 1 23 6 1 24 1 1 25 79 1 26 43 1 27 12 1 28 57 1 29 96 1 30 7 1 31 28 1 32 62 1 33 21 1 34 32 1 35 80 1 36 75 1 37 29 1 38 21 1 ...
output:
50000
result:
ok single line: '50000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
22 4 7 22 1 1 22 1 22 8 1 22 21 1 21 2 1 21 9 1 21 20 1 3 20 1 10 20 1 19 20 1 19 18 1 4 18 1 11 18 1 17 18 1 17 12 1 17 16 1 16 5 1 16 15 1 15 14 1 15 6 1 15 13 1 1 8 6 13
output:
12
result:
ok single line: '12'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
36 5 1 21 1 2 21 2 21 30 3 30 22 4 22 3 5 22 4 6 30 36 7 36 20 8 36 19 9 30 29 10 29 18 11 29 17 12 30 28 13 28 16 14 28 15 15 28 14 16 32 30 17 32 23 18 23 5 19 23 24 20 24 6 21 24 7 22 32 34 23 34 27 24 27 13 25 12 34 26 34 35 27 35 25 28 25 8 29 25 9 30 35 33 31 31 26 32 26 11 33 31 10 34 31 33 3...
output:
9
result:
ok single line: '9'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
36 6 1 21 1 2 21 2 21 30 3 30 22 4 22 3 5 22 4 6 30 36 7 36 20 8 36 19 9 30 29 10 29 18 11 29 17 12 30 28 13 28 16 14 28 15 15 28 14 16 32 30 17 32 23 18 23 5 19 23 24 20 24 6 21 24 7 22 32 34 23 34 27 24 27 13 25 12 34 26 34 35 27 35 25 28 25 8 29 25 9 30 35 33 31 31 26 32 26 11 33 31 10 34 31 33 3...
output:
17
result:
ok single line: '17'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
25 3 1 2 1 1 3 2 2 4 3 2 5 4 3 6 5 3 7 6 4 8 7 4 9 8 5 10 9 5 11 10 6 12 11 6 13 12 7 14 13 7 15 14 8 16 15 8 17 16 9 18 17 9 19 18 10 20 19 10 21 20 14 22 21 14 23 22 15 24 23 15 25 24 1 16 25
output:
9
result:
ok single line: '9'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
9 3 1 2 8 2 4 7 4 3 6 4 6 4 5 6 3 6 7 2 6 9 5 9 8 6 2 5 8
output:
6
result:
ok single line: '6'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
25 10 1 2 1 1 3 2 2 4 3 2 5 4 3 6 5 3 7 6 4 8 7 4 9 8 5 10 9 5 11 10 6 12 11 6 13 12 7 14 13 7 15 14 8 16 15 8 17 16 9 18 17 9 19 18 10 20 19 10 21 20 14 22 21 14 23 22 15 24 23 15 25 24 16 17 18 19 20 21 22 23 24 25
output:
21
result:
ok single line: '21'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
10 3 4 9 71 10 8 869 6 7 536 9 3 682 5 1 782 7 1 723 7 2 659 2 8 520 2 9 858 2 9 10
output:
4
result:
ok single line: '4'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
111 47 15 102 348 99 80 668 100 23 255 101 62 744 51 64 644 63 6 537 21 8 504 78 91 696 3 88 796 20 59 502 21 68 687 26 72 31 33 93 77 96 73 594 91 105 159 106 53 470 86 89 608 91 25 278 104 71 656 26 99 125 41 69 766 31 3 129 39 20 904 24 52 878 3 96 470 95 35 378 23 82 567 86 52 864 82 10 137 4 92...
output:
71
result:
ok single line: '71'
Test #14:
score: 0
Accepted
time: 4ms
memory: 3884kb
input:
5000 427 1409 1882 836 3993 4243 743 700 4344 602 3001 2843 662 2791 74 183 3486 4777 775 3960 3734 431 456 745 307 4766 853 863 4469 450 272 381 4861 284 1747 2637 158 4727 2821 153 1342 1441 783 3953 2216 793 1677 2397 647 1428 1260 958 2652 1600 127 1437 1126 471 1062 2325 898 1788 1826 890 1188 ...
output:
1167
result:
ok single line: '1167'
Test #15:
score: 0
Accepted
time: 32ms
memory: 6288kb
input:
49990 18606 16521 24849 183 39648 48711 673 22572 4321 612 46032 8301 193 8413 5870 611 2822 47588 791 36695 16916 490 20411 33115 773 24452 16923 534 33824 8971 771 20160 9555 479 12040 14019 565 44728 15446 751 32371 20723 374 9376 31976 646 33503 28501 264 44301 1126 655 47381 17014 456 22824 164...
output:
29362
result:
ok single line: '29362'
Test #16:
score: 0
Accepted
time: 7ms
memory: 3932kb
input:
9999 2756 9844 5 437 7324 3408 941 4777 8454 247 1478 5367 609 2108 8662 885 6625 1897 286 2448 8159 530 6694 6545 482 2542 4146 11 3379 4110 165 4631 5493 275 2969 9845 323 4988 9071 786 6793 9888 968 6058 2423 808 6296 9363 871 8064 1070 993 9486 2234 654 8797 2109 448 3416 5595 932 6057 2433 455 ...
output:
4960
result:
ok single line: '4960'
Test #17:
score: 0
Accepted
time: 11ms
memory: 4572kb
input:
19999 8629 863 219 816 3754 10458 833 17884 8472 538 9332 4306 616 9426 1916 112 6738 12178 550 6578 17780 274 10770 1483 349 19337 13639 224 13264 18150 596 19921 17706 858 152 4745 887 168 3097 686 820 2994 932 10879 14784 775 3897 17861 12 12053 19335 102 3788 13637 517 7602 19046 170 12518 13873...
output:
12741
result:
ok single line: '12741'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
3312 1091 14 259 914 3111 78 917 1861 1835 58 3057 2799 310 940 3199 59 2490 132 178 462 2114 312 1556 575 692 1534 2116 499 2740 174 601 2387 947 249 218 143 519 315 2640 55 3010 913 122 1395 2608 148 2461 504 157 110 732 912 2998 3028 480 2936 277 282 2499 1742 401 1458 2736 139 968 1754 92 2005 1...
output:
1792
result:
ok single line: '1792'
Test #19:
score: 0
Accepted
time: 4ms
memory: 3892kb
input:
4311 2103 2141 2773 140 18 473 53 53 2244 816 1827 3895 635 2359 988 917 1492 2580 424 1805 4060 661 2292 3113 236 2177 1177 171 3872 1277 105 71 4189 335 332 2505 287 318 954 1000 3964 4038 681 3469 4285 6 3959 1823 655 2543 3059 616 4222 3554 42 2453 3838 200 1034 4185 991 3842 120 133 339 1911 27...
output:
2967
result:
ok single line: '2967'
Test #20:
score: 0
Accepted
time: 10ms
memory: 4128kb
input:
14311 3224 6832 5712 113 5205 1928 642 4423 73 646 896 10553 343 7871 10112 928 6413 7116 924 3103 13968 748 12567 2947 104 7156 54 430 5390 10535 42 2843 8925 225 12768 4948 689 6948 4619 218 988 6340 93 5352 12086 542 13174 175 838 8062 5649 381 8759 5337 447 6646 13449 77 8265 2206 771 9546 8706 ...
output:
6225
result:
ok single line: '6225'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
4 4 1 2 1 1 3 1 1 4 1 2 4 1 3
output:
4
result:
ok single line: '4'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
1137 275 195 320 189 540 1064 860 548 334 288 230 319 996 428 226 300 1082 957 241 509 1134 307 857 847 72 410 449 333 1115 581 88 418 961 764 397 1117 438 290 826 868 1053 254 727 973 139 990 602 340 543 890 402 451 1112 50 57 1108 275 543 34 717 173 1094 1017 242 73 421 296 88 1050 411 550 359 996...
output:
513
result:
ok single line: '513'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
1835 894 1138 378 650 1214 1180 86 1132 302 572 788 230 930 415 1553 853 405 572 462 1770 1694 924 185 658 835 299 839 696 925 1429 393 968 450 364 831 1617 296 1429 565 792 1728 443 641 14 598 837 66 247 50 1398 840 295 703 1682 155 341 857 139 347 1293 384 611 1250 892 1418 401 325 1557 795 405 13...
output:
1265
result:
ok single line: '1265'
Test #24:
score: 0
Accepted
time: 23ms
memory: 5140kb
input:
31835 12143 12096 10495 444 249 21585 856 2745 11663 268 20437 31191 57 16181 16405 961 13583 10433 81 28317 11721 961 1603 21697 743 8069 1521 45 26485 22724 930 7607 28522 908 7364 11641 299 15827 11232 317 3899 14114 807 11491 28930 331 2987 13549 105 11145 7700 347 11099 23482 974 28497 10375 55...
output:
18865
result:
ok single line: '18865'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
35 11 7 18 455 27 10 574 15 26 5 11 31 458 35 22 690 28 27 213 33 19 203 11 1 927 17 9 204 24 12 85 24 16 782 29 14 258 6 35 764 29 27 539 29 25 739 7 3 869 1 5 485 25 20 145 2 20 188 8 13 965 23 26 310 8 19 452 32 9 888 6 8 180 20 5 245 24 9 808 8 34 358 5 24 500 23 3 463 34 21 815 5 21 694 4 23 32...
output:
19
result:
ok single line: '19'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
27 11 19 6 921 19 15 982 10 27 927 8 16 449 26 11 563 23 27 778 24 3 881 22 26 454 20 26 915 19 25 277 16 9 644 19 13 335 4 17 454 2 4 510 1 21 98 26 4 564 12 14 667 18 7 398 4 21 676 3 12 498 16 13 523 16 12 984 16 21 541 18 16 399 5 18 774 5 23 172 27 19 16 23 8 5 18 24 13 14 9
output:
13
result:
ok single line: '13'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
129 20 47 98 191 103 8 394 105 125 279 45 22 348 1 67 883 53 65 826 15 73 202 32 82 341 62 128 330 12 91 283 47 42 362 82 60 292 122 59 131 71 96 697 16 6 721 107 75 672 35 78 754 93 126 445 50 35 315 37 107 963 11 68 840 5 58 485 127 114 549 17 55 18 119 110 8 24 55 113 96 28 126 97 128 462 9 38 84...
output:
39
result:
ok single line: '39'
Test #28:
score: 0
Accepted
time: 29ms
memory: 5796kb
input:
39129 19040 38615 23915 814 37313 21170 952 19258 24331 734 24984 16708 130 37174 25810 818 37424 11775 430 32046 38253 722 10474 38980 223 10058 20383 24 32335 23712 540 19213 26335 803 23904 30563 490 15256 25079 574 12547 29787 830 37466 16616 860 9650 27353 145 31030 21246 233 13961 7022 661 389...
output:
26726
result:
ok single line: '26726'
Test #29:
score: 0
Accepted
time: 51ms
memory: 7644kb
input:
69119 15860 3029 30167 896 43308 36239 625 66082 29655 197 6400 4504 941 17230 67487 181 68764 38509 716 26632 41830 509 33679 58442 910 42265 12926 273 54706 39482 956 4472 60604 753 3964 65162 500 55908 64486 516 1431 43425 485 17731 2994 953 44067 52869 909 26371 30511 514 35657 7641 306 54239 60...
output:
30385
result:
ok single line: '30385'
Test #30:
score: 0
Accepted
time: 70ms
memory: 9520kb
input:
99993 11085 65492 17811 566 80773 64201 660 80583 35944 362 14561 28119 74 18175 89278 666 56628 64999 764 19678 9678 640 68210 56925 788 68160 67432 41 99491 80268 861 76300 83789 152 33205 2036 952 11352 4005 975 99563 41863 912 60397 93323 56 44983 93673 459 97143 46359 907 587 70323 540 16150 27...
output:
27368
result:
ok single line: '27368'
Test #31:
score: 0
Accepted
time: 76ms
memory: 9404kb
input:
99199 16960 23538 95853 535 92251 63359 450 3594 34747 183 36478 54742 544 95835 2600 112 82172 34759 141 56749 77281 493 52330 12531 780 53904 89330 567 56792 86527 725 58089 9889 60 83571 18052 2 69829 26299 787 72550 68581 958 3805 35300 168 27324 63948 563 40954 76422 466 66461 3171 440 67791 60...
output:
36015
result:
ok single line: '36015'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
3 2 1 2 430 1 3 347 3 1
output:
2
result:
ok single line: '2'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
3 1 1 2 11 2 3 5 2
output:
1
result:
ok single line: '1'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
3 3 1 2 11 2 3 5 2 1 3
output:
3
result:
ok single line: '3'