QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#258263 | #2272. Formica Sokobanica | Fireball0424# | WA | 47ms | 58304kb | C++14 | 1.8kb | 2023-11-19 16:33:03 | 2023-11-19 16:33:04 |
Judging History
answer
#pragma GCC optimizer("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define int long long
#define ld long double
#define ull unsigned long long
#define fr first
#define fi first
#define sc second
#define se second
#define all(x) x.begin(), x.end()
#define pii pair<int,int>
using namespace std;
#ifndef fireball
#define tofu ios::sync_with_stdio(0); cin.tie(0);
#else
#define tofu freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif
void db() {cout << '\n';}
template <typename T, typename ...U> void db(T a, U ...b) {cout << a << ' ', db(b...);}
signed main(){
tofu;
int n, m;
cin >> n >> m;
vector<int> g[n + 1];
for(int i = 1; i < n; ++i){
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
int a[n + 1] = {};
for(int i = 0; i < m; ++i){
int x; cin >> x;
a[x] = 1;
}
int vis[n + 1] = {};
function<void(int,int, int)> dfs = [&](int u, int pa, int f){
vis[pa] = 1;
if(g[u].size() == 1){
if(f == 0) vis[u] = 1;
return;
}
int has = 0;
for(int i : g[u]) if(i != pa and !a[i]) has++;
for(int i : g[u]){
if(i == pa) continue;
if(a[i]){
if(f == 0) dfs(i, u, 1);
else if(has) dfs(i, u, 1);
}
else{
if(has > 1) dfs(i, u, 0);
else dfs(i, u, f);
}
}
};
for(int i : g[1]){
if(a[i]) dfs(i, 1, 1);
else dfs(i, 1, 0);
}
//for(int i = 1; i <= n; ++i) db(i, vis[i]);
int ans = 0;
for(int i = 1; i <= n; ++i) ans += vis[i];
db(ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 35ms
memory: 19008kb
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: 27ms
memory: 18992kb
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: 47ms
memory: 58304kb
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: 44ms
memory: 58292kb
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: -100
Wrong Answer
time: 0ms
memory: 3612kb
input:
1 0
output:
0
result:
wrong answer 1st lines differ - expected: '1', found: '0 '