QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#28192 | #2272. Formica Sokobanica | Suika_predator# | AC ✓ | 113ms | 31156kb | C++20 | 766b | 2022-04-12 19:07:22 | 2022-04-29 09:14:42 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 210000;
int n,m;
vector<int>V[maxn];
int o[maxn];
int ans;
void dfs(const int x,const int fa,int c)
{
int s=0;
for(auto y:V[x]) if(y!=fa)
{
s+= o[y]==0;
}
if(c+o[x]==0) ans++;
else if(c+o[x]==1)
{
if(s>=1) c=1,ans++;
else return;
}
else return;
for(auto y:V[x]) if(y!=fa)
{
if(o[y]==0)
dfs(y,x,s>1?0:c);
else
dfs(y,x,s>0?0:c);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<n;i++)
{
int x,y; cin>>x>>y;
V[x].push_back(y);
V[y].push_back(x);
}
for(int i=1;i<=m;i++)
{
int x; cin>>x;
o[x]=1;
}
dfs(1,0,0);
cout<<ans<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 51ms
memory: 16128kb
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: 51ms
memory: 16012kb
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: 94ms
memory: 31156kb
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: 98ms
memory: 30832kb
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: 5ms
memory: 8508kb
input:
1 0
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 2ms
memory: 8936kb
input:
2 0 2 1
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 5ms
memory: 8944kb
input:
2 1 2 1 2
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 108ms
memory: 15700kb
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: 113ms
memory: 15628kb
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: 87ms
memory: 15708kb
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: 96ms
memory: 15700kb
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: 99ms
memory: 15652kb
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: 6ms
memory: 8780kb
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: 3ms
memory: 9120kb
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: 52ms
memory: 23416kb
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'