QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#296578#6307. Chase Game 2tangledWA 6ms3556kbC++201.2kb2024-01-03 10:39:272024-01-03 10:39:27

Judging History

你现在查看的是最新测评结果

  • [2024-01-03 10:39:27]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3556kb
  • [2024-01-03 10:39:27]
  • 提交

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'