QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#244168#2272. Formica SokobanicaNYCU_gAwr_gurA#AC ✓64ms30144kbC++171.3kb2023-11-08 21:40:492023-11-08 21:40:49

Judging History

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

  • [2023-11-08 21:40:49]
  • 评测
  • 测评结果:AC
  • 用时:64ms
  • 内存:30144kb
  • [2023-11-08 21:40:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define fast
#else
#define fast cin.tie(0)->sync_with_stdio(0)
#define cerr if(1);else cerr
#define endl '\n'
#endif
#define _ <<' '<<
#define ALL(v) v.begin(),v.end()
#define ft first
#define sd second

using ll = long long;
using ld = long double;
using pii = pair<int,int>;

const int maxn = 2e5+50;
vector<int> G[maxn];
int has[maxn];

int ans = 0;

void dfs(int cur, int fa, bool gg) {
    if (has[cur] && gg) return;

    cerr _ "dfs" _ cur _ fa _ gg _ endl;

    int can = 0;
    for (int &nxt : G[cur]) {
        if (nxt == fa) continue;
        can += !has[nxt];
    }

    gg |= has[cur];

    if (can || !gg) {
        cerr << "can : " << cur << endl;
        ++ans;
    }
    
    for (int &nxt : G[cur]) {
        if (nxt != fa) {
            if ((can - !has[nxt])) dfs(nxt, cur, 0);
            else dfs(nxt, cur, gg);
        }
    }
}


signed main() {
    fast;

    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for (int i = 0; i < k; ++i) {
        int x; cin >> x;
        has[x] = 1;
    }

    dfs(1,1,0);

    cout << ans << endl;

    cerr _ "meow" _ endl;

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 38ms
memory: 15648kb

input:

200000 67431
1 134415
1 3
1 4
11 1
13 1
19 1
1 25
31 1
1 33
41 1
46 1
48 1
1 52
1 55
60 1
63 1
1 77
78 1
85 1
1 86
1 87
90 1
92 1
95 1
1 96
1 98
1 103
1 115
1 123
1 126
1 128
1 130
137 1
140 1
141 1
1 142
153 1
162 1
165 1
167 1
1 169
1 170
177 1
1 187
1 189
1 190
1 193
1 197
202 1
1 216
1 220
1 222...

output:

132569

result:

ok single line: '132569'

Test #2:

score: 0
Accepted
time: 21ms
memory: 15616kb

input:

200000 66498
1 50279
1 213
1 218
220 1
1 224
1 229
1 232
1 236
239 1
1 240
1 244
246 1
247 1
1 255
1 257
1 260
271 1
276 1
278 1
1 280
282 1
1 288
292 1
293 1
300 1
1 303
1 309
1 312
1 317
321 1
322 1
326 1
327 1
328 1
340 1
342 1
346 1
1 352
1 363
366 1
368 1
370 1
374 1
382 1
384 1
1 389
1 392
393...

output:

133502

result:

ok single line: '133502'

Test #3:

score: 0
Accepted
time: 48ms
memory: 29964kb

input:

200000 1
395 397
792 125000
792 796
797 798
800 799
801 800
803 805
807 805
807 808
809 808
812 813
818 816
820 821
821 822
825 826
826 829
829 831
831 832
833 836
836 839
840 839
841 840
842 844
847 845
851 849
851 853
871 872
873 875
878 875
881 879
886 887
894 895
900 897
901 903
908 909
911 909
...

output:

199999

result:

ok single line: '199999'

Test #4:

score: 0
Accepted
time: 45ms
memory: 30144kb

input:

200000 0
80643 20559
100001 3
3 4
7 6
7 9
10 9
10 11
11 14
23 24
25 24
27 26
28 27
33 31
38 39
40 39
41 40
41 42
45 42
45 46
47 46
47 49
50 49
51 50
51 53
54 53
54 57
58 57
58 59
61 59
63 66
68 66
71 70
71 73
73 78
78 79
85 82
91 89
95 94
95 97
97 98
101 103
104 109
110 111
114 111
117 114
127 126
1...

output:

200000

result:

ok single line: '200000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 8088kb

input:

1 0

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 8088kb

input:

2 0
2 1

output:

2

result:

ok single line: '2'

Test #7:

score: 0
Accepted
time: 0ms
memory: 8272kb

input:

2 1
2 1
2

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 64ms
memory: 15224kb

input:

200000 66659
199145 199147
1 982
995 1
1021 1
1141 1
1 4370
1 21842
1 31917
67858 1
1 6658
106770 1
1 176182
1 92830
176182 82908
163205 151261
163205 69945
25981 151261
84701 151261
133323 25981
3569 67662
144579 102158
51901 136200
39443 51901
39443 105504
188083 73666
160799 73666
110052 44678
31...

output:

120758

result:

ok single line: '120758'

Test #9:

score: 0
Accepted
time: 57ms
memory: 15216kb

input:

200000 66968
66506 66507
5 1
14 1
1 934
8938 1
94914 1
129811 1
139338 1
8798 1
14068 1
14068 18416
151802 14068
25746 36129
65840 41866
13509 65840
117038 70185
84160 137145
84160 15443
58812 62199
76227 28972
76227 196465
196465 164019
9905 164019
78396 15443
48759 60484
133137 157681
157681 16135...

output:

120712

result:

ok single line: '120712'

Test #10:

score: 0
Accepted
time: 55ms
memory: 15132kb

input:

200000 67031
191072 107575
1 4
7 1
1 27
1 47
885 1
1490 1
1 1618
1955 1
160680 195231
187215 145694
1423 145694
145694 64694
76990 64694
66007 76990
53465 187215
142082 58463
154373 142082
142082 176661
87244 150526
59028 121714
176339 96831
33799 44937
35556 116963
142634 134416
182185 134416
18218...

output:

120352

result:

ok single line: '120352'

Test #11:

score: 0
Accepted
time: 61ms
memory: 15112kb

input:

200000 66658
28401 13192
566 1
583 1
1 602
613 1
1 747
11346 1
20833 1
25460 1
126405 86462
105847 65744
25460 123884
25460 23899
25460 153852
148186 180942
23899 7187
119304 62937
62937 182283
155697 80330
85277 162166
66587 76290
76290 95369
55250 112646
48221 119337
163176 48221
138844 48221
1984...

output:

120083

result:

ok single line: '120083'

Test #12:

score: 0
Accepted
time: 51ms
memory: 15220kb

input:

200000 66537
113173 113172
1 392
397 1
484 1
557 1
1 1065
9876 1
15191 1
22828 1
1 26743
73849 1
120289 1
1 6546
40242 118132
118132 2913
172356 69444
6546 168120
6546 40270
109844 6546
188247 6546
188247 36151
36235 36151
30807 115638
40270 75913
93198 159567
183280 104850
157068 99352
66991 155551...

output:

121703

result:

ok single line: '121703'

Test #13:

score: 0
Accepted
time: 0ms
memory: 8404kb

input:

5000 1660
1865 1866
5 1
273 1
1 502
1054 1
1 4782
1 3426
1 2263
1 3083
4899 2140
2140 1772
371 2152
4118 3083
4066 3083
4118 2613
3807 2369
2613 3021
1826 2613
2263 2668
3395 4761
3522 4885
1063 4884
1063 4271
1063 2270
1063 3056
2270 2674
2271 1666
2307 4000
4000 1035
4296 4535
3408 1317
4685 3408
...

output:

3080

result:

ok single line: '3080'

Test #14:

score: 0
Accepted
time: 0ms
memory: 8288kb

input:

5000 1645
689 690
27 1
1 50
128 1
1 207
506 1
1 1069
4191 1
2644 2328
2838 2644
722 51
3005 722
3005 2123
2913 3345
1972 1876
4672 129
3366 1647
2886 1647
2895 3558
368 3095
4746 3667
2382 4746
4578 4746
4578 2109
3669 2961
3905 2961
2382 1471
4804 1134
4804 2170
1283 2170
3184 1283
3184 4501
3039 1...

output:

3045

result:

ok single line: '3045'

Test #15:

score: 0
Accepted
time: 37ms
memory: 22156kb

input:

200000 0
1 2
1 3
3 4
3 5
5 6
5 7
7 8
7 9
9 10
9 11
11 12
11 13
13 14
13 15
15 16
15 17
17 18
17 19
19 20
19 21
21 22
21 23
23 24
23 25
25 26
25 27
27 28
27 29
29 30
29 31
31 32
31 33
33 34
33 35
35 36
35 37
37 38
37 39
39 40
39 41
41 42
41 43
43 44
43 45
45 46
45 47
47 48
47 49
49 50
49 51
51 52
51 ...

output:

200000

result:

ok single line: '200000'