QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#296578 | #6307. Chase Game 2 | tangled | WA | 6ms | 3556kb | C++20 | 1.2kb | 2024-01-03 10:39:27 | 2024-01-03 10:39:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using i64 = long long;
void solve()
{
int n;
cin >> n;
vector<int> e[n + 1], d(n + 1);
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
d[u]++, d[v]++;
}
vector<int> f(n + 1);
function<void(int u, int fa)> dfs = [&](int u, int fa)
{
f[u] = fa;
for (auto v : e[u])
{
if (v == fa)
continue;
dfs(v, u);
}
};
dfs(1, 0);
int ans = (count(d.begin() + 2, d.end(), 1) + 1) / 2;
map<int, int> mp;
for (int i = 2; i <= n; i++)
if (d[i] == 1)
mp[f[i]]++;
for (auto [x, y] : mp)
{
if (mp.size() == 1 && f[f[x]] == 0)
return void(cout << -1 << endl);
if (y >= 2)
{
ans -= (y + 1) / 2;
ans += y;
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1;
cin >> tc;
while (tc--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
input:
4 2 1 2 4 1 2 2 3 3 4 4 1 2 2 3 2 4 5 1 2 2 3 3 4 3 5
output:
-1 1 -1 2
result:
ok 4 number(s): "-1 1 -1 2"
Test #2:
score: -100
Wrong Answer
time: 6ms
memory: 3556kb
input:
10000 4 1 2 1 3 3 4 4 1 2 1 3 1 4 4 1 2 2 3 1 4 5 1 2 2 3 1 4 4 5 5 1 2 2 3 3 4 4 5 4 1 2 2 3 2 4 5 1 2 1 3 2 4 2 5 4 1 2 2 3 1 4 5 1 2 1 3 2 4 1 5 5 1 2 2 3 3 4 2 5 5 1 2 1 3 2 4 2 5 4 1 2 1 3 3 4 5 1 2 1 3 3 4 1 5 4 1 2 1 3 1 4 5 1 2 1 3 3 4 3 5 5 1 2 2 3 3 4 3 5 4 1 2 1 3 2 4 5 1 2 2 3 2 4 3 5 5 ...
output:
1 -1 1 1 1 -1 3 1 3 1 3 1 3 -1 3 2 1 1 3 1 1 1 -1 3 1 2 1 -1 1 1 3 1 1 -1 1 3 1 1 1 -1 1 1 2 3 3 1 1 1 -1 1 1 1 1 1 1 3 1 1 3 -1 -1 -1 2 3 3 1 1 1 3 3 3 -1 1 3 -1 1 1 -1 3 -1 -1 1 3 3 1 1 1 1 1 1 1 1 1 1 3 -1 1 1 3 -1 3 1 1 1 -1 3 -1 1 -1 -1 3 -1 3 1 2 3 1 1 1 1 1 1 1 1 1 -1 1 1 3 1 1 1 1 1 1 1 3 -1...
result:
wrong answer 7th numbers differ - expected: '2', found: '3'