QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#739401 | #2272. Formica Sokobanica | k1nsom | WA | 24ms | 18856kb | C++14 | 1.5kb | 2024-11-12 21:40:33 | 2024-11-12 21:40:40 |
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 dfs1(int u, int fa)
{
int cnt = 0;
for (auto to : e[u])
if (to != fa)
{
cnt++;
dfs1(to, u);
if (!vis[to])
mx[u] = max(mx[to], mx[u]);
}
mx[u] = max(mx[u], cnt);
}
void dfs(int u, int fa, int ok)
{
if (ok == 2)
{
return;
}
ans++;
if (vis[u])
{
if (mx[u] >= 2)
{
for (auto to : e[u])
if (to != fa)
dfs(to, u, ok);
}
else
{
for (auto to : e[u])
if (to != fa)
{
ans--;
dfs(to, u, ok + 1);
}
}
}
else
{
for (auto to : e[u])
if (to != fa)
dfs(to, u, ok);
}
}
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;
}
dfs1(1, 0);
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: 0
Wrong Answer
time: 24ms
memory: 18856kb
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:
200000
result:
wrong answer 1st lines differ - expected: '132569', found: '200000'