QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#28237 | #2272. Formica Sokobanica | icypigeon# | AC ✓ | 93ms | 27416kb | C++11 | 1.3kb | 2022-04-12 21:26:03 | 2022-04-29 09:18:55 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
using namespace std;
vector<int> a;
vector< vector<int> > g;
int ans = 0;
void dfs(int cur, int pre, int state) {
// cout << cur << ' ' << pre << ' ' << state << endl;
int c0 = 0, c1 = 0;
for(int ver : g[cur]) if(ver != pre) {
if(a[ver]) ++ c1;
else ++ c0;
}
state |= a[cur];
// cout << c0 << ' ' << c1 << ' ' << state << endl << endl;
if(!state) {
++ ans;
for(int ver : g[cur]) if(ver != pre) dfs(ver, cur, 0);
} else {
if(c0 == 0) return ;
++ ans;
for(int ver : g[cur]) if(ver != pre) dfs(ver, cur, c0 == 1);
}
}
int main() {
if(fopen("yl.in", "r")) {
freopen("yl.in", "r", stdin);
freopen("yl.out", "w", stdout);
}
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m, u, v;
cin >> n >> m;
a.resize(n + 1);
g.resize(n + 1);
rep(i,1,n - 1) {
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
rep(i,1,m) {
cin >> u;
a[u] = 1;
}
dfs(1, 0, 0);
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 42ms
memory: 15684kb
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: 57ms
memory: 15880kb
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: 79ms
memory: 27360kb
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: 73ms
memory: 27416kb
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: 3ms
memory: 3564kb
input:
1 0
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 3ms
memory: 3588kb
input:
2 0 2 1
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
2 1 2 1 2
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 93ms
memory: 14920kb
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: 92ms
memory: 15080kb
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: 77ms
memory: 14880kb
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: 93ms
memory: 14992kb
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: 83ms
memory: 15136kb
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: 1ms
memory: 3884kb
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: 1ms
memory: 3876kb
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: 48ms
memory: 21136kb
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'