QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#739520 | #2272. Formica Sokobanica | k1nsom | WA | 44ms | 31936kb | C++14 | 1.1kb | 2024-11-12 22:00:05 | 2024-11-12 22:00:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int, int>
const int N = 2e5 + 5;
int n, m, ans, vis[N], mx[N];
vector<int> e[N];
void dfs(int u, int fa, int ok)
{
vis[u] |= ok;
int cnt = 0;
for (auto to : e[u])
if (to != fa && !vis[to])
cnt++;
if (cnt || vis[u] == 0)
ans++;
for (auto to : e[u])
if (to != fa)
{
cnt -= vis[to] == 0;
if (cnt >= 1)
dfs(to, u, 0);
else
dfs(to, u, vis[to]);
cnt += vis[to] == 0;
}
}
void solve()
{
cin >> n >> m;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
for (int i = 1; i <= m; i++)
{
int x;
cin >> x;
vis[x] = 1;
}
dfs(1, 0, 0);
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
while (t--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 37ms
memory: 18812kb
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: 37ms
memory: 18388kb
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: -100
Wrong Answer
time: 44ms
memory: 31936kb
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:
200000
result:
wrong answer 1st lines differ - expected: '199999', found: '200000'