QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#464222#2524. Dessert CaféThirvinAC ✓56ms17904kbC++141.6kb2024-07-05 22:36:392024-07-05 22:36:40

Judging History

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

  • [2024-07-05 22:36:40]
  • 评测
  • 测评结果:AC
  • 用时:56ms
  • 内存:17904kb
  • [2024-07-05 22:36:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
int dfs(int cur, int pre, vector<vector<int>> &v, vector<int> &cnt,set<int> &st){
        int tmp = 0;
        if(st.find(cur) != st.end())
                tmp = 1;

        for(int i : v[cur]){
                if(i == pre){
                        continue;
                }
                tmp += dfs(i, cur, v, cnt, st);
        }
        cnt[cur] = tmp;
        return tmp > 0;
}
void ff(int cur, int pre, vector<vector<int>> &v, vector<int> &cnt){
        if(cnt[pre] > cnt[cur])
                cnt[cur] += 1;

        for(int it : v[cur]){
                if(it == pre)
                        continue;
                ff(it, cur, v, cnt);
        }
}
void solve(){
        int n,k;
        cin >> n >> k;
        vector<vector<int>> v(n+1);
        for(int i = 0;i < n - 1;i ++){
                int a,b,k;
                cin >> a >> b >> k;
                v[a].emplace_back(b);
                v[b].emplace_back(a);
        }
        set<int> st;
        for(int i = 0;i < k;i ++){
                int x;
                cin >> x;
                st.emplace(x);
        }
        vector<int> cnt(n+1);
        dfs(1, 0, v, cnt, st);
        ff(1, 0, v, cnt);
        int ans = 0;
        for(int i = 0;i < n;i ++){
                if(cnt[i+1] >= 2 || st.find(i+1) != st.end()){
                        ans ++ ;
                }
        }
        cout << ans << "\n";
}
int main(){
        cin.tie(0)->sync_with_stdio(0);
        int t = 1;
        while(t--){
                solve();
        }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3820kb

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: 27ms
memory: 14076kb

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: 56ms
memory: 17904kb

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: 13ms
memory: 9536kb

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: 25ms
memory: 11552kb

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: 3628kb

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: 3848kb

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: 3624kb

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: 3556kb

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: 0ms
memory: 3732kb

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: 3556kb

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: 3624kb

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: 3628kb

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: 2ms
memory: 3944kb

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: 27ms
memory: 7016kb

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: 4ms
memory: 4128kb

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: 10ms
memory: 4932kb

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: 3816kb

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: 0ms
memory: 4212kb

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: 6ms
memory: 4304kb

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: 3624kb

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: 3648kb

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: 1ms
memory: 3708kb

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: 16ms
memory: 5788kb

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: 3624kb

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: 3564kb

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: 3636kb

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: 20ms
memory: 6624kb

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: 39ms
memory: 8112kb

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: 46ms
memory: 9776kb

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: 50ms
memory: 9916kb

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: 3816kb

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: 3788kb

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: 3492kb

input:

3 3
1 2 11
2 3 5
2 1 3

output:

3

result:

ok single line: '3'