QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#401940 | #2272. Formica Sokobanica | dohoon# | WA | 46ms | 30256kb | C++17 | 776b | 2024-04-29 16:58:36 | 2024-04-29 16:58:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MXN = 2e5+5;
int A[MXN];
vector<int> E[MXN];
int dfs(int x,int p,int v){
v+=A[x];
if(v>1) return 0;
int me = !v, ret = 0;
int emp = 0, down = 0;
for(int i : E[x]) if(i^p) down++, emp += !A[i];
if(emp && v) me = 1, emp--;
if(emp>1 || (down!=1 && emp>0)) v = 0;
for(int i : E[x]) if(i^p){
ret += dfs(i,x,v);
}
return ret+me;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q; cin >> n >> q;
for(int i = 1;i<n;i++){
int a,b; cin >> a >> b;
E[a].push_back(b);
E[b].push_back(a);
}
for(int i = 0;i<q;i++){
int a; cin >> a;
A[a]++;
}
cout << dfs(1,0,0);
}
详细
Test #1:
score: 100
Accepted
time: 34ms
memory: 15572kb
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: 22ms
memory: 15684kb
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: 46ms
memory: 30188kb
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: 35ms
memory: 30256kb
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: 8204kb
input:
1 0
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 1ms
memory: 8236kb
input:
2 0 2 1
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 2ms
memory: 8240kb
input:
2 1 2 1 2
output:
1
result:
ok single line: '1'
Test #8:
score: -100
Wrong Answer
time: 45ms
memory: 15416kb
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:
108420
result:
wrong answer 1st lines differ - expected: '120758', found: '108420'