QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#738677 | #2272. Formica Sokobanica | Shuishui | WA | 57ms | 40140kb | C++14 | 1.4kb | 2024-11-12 19:41:43 | 2024-11-12 19:41:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define Sz(x) (int)(x).size()
#define bit(x) (1ll << (x))
using ll = long long;
using db = double;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vd = vector<db>;
mt19937 mrand(time(0));
void solve(void)
{
int n, m;
cin >> n >> m;
vii e(n + 2);
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
e[u].pb(v);
e[v].pb(u);
}
vi a(n + 2);
for (int i = 1; i <= m; i++)
{
int x;
cin >> x;
a[x] = 1;
}
int ans = 0;
function<void(int, int, int)> dfs = [&](int u, int fa, int tp)
{
a[u] |= tp;
int cnt = 0;
for (auto v : e[u]) if (v != fa)
if (a[v] == 0)
cnt++;
if (cnt || !a[u]) ans++;
// cerr << u << " " << cnt << "\n";
for (auto v : e[u]) if (v != fa)
{
cnt -= (a[v] == 0);
if (cnt >= 1)
dfs(v, u, 0);
else
{
if (!(a[v] && a[u]))
dfs(v, u, a[u]);
}
cnt += (a[v] == 0);
}
};
dfs(1, 0, 0);
cout << ans << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
// cout << fixed << setprecision(10);
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 28ms
memory: 15808kb
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: 30ms
memory: 15812kb
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: 44ms
memory: 40140kb
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: 48ms
memory: 39976kb
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: 3724kb
input:
1 0
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
2 0 2 1
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 1 2 1 2
output:
1
result:
ok single line: '1'
Test #8:
score: -100
Wrong Answer
time: 57ms
memory: 14996kb
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:
115134
result:
wrong answer 1st lines differ - expected: '120758', found: '115134'