QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#689921#6307. Chase Game 2blue_sky#WA 7ms3588kbC++204.9kb2024-10-30 19:14:292024-10-30 19:14:29

Judging History

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

  • [2024-10-30 19:14:29]
  • 评测
  • 测评结果：WA
  • 用时：7ms
  • 内存：3588kb
查看
  • [2024-10-30 19:14:29]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define bug(X) cout << "bug:# " << X << endl
#define bug2(f, X) cout << "bug:# " << f << " " << X << endl
#define bug3(i, j, G) cout << "bug:# " << i << ' ' << j << ' ' << G << endl
#define endl '\n'
using namespace std;
const int mod = 998244353;
const int N = 10 + 5e5;
void _();
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        _();
    return 0;
}

void _()
{
    int n;
    cin >> n;
    vector<int> in(n + 1);
    vector<vector<int>> e(n + 1);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
        in[u]++;
        in[v]++;
    }

    int leaf = 0;
    vector<int> vis(n + 1), d(n + 1, 1e18);
    queue<int> q;
    d[1] = 0;
    q.push(1);
    while (q.size())
    {
        int u = q.front();
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto v : e[u])
        {
            d[v] = min(d[v], d[u] + 1);
            q.push(v);
        }
    }
    map<int, int> root;
    for (int i = 2; i <= n; i++)
        if (in[i] == 1)
        {
            leaf++;
            root[d[i]]++;
        }
    map<int, int> d_cnt;
    for (auto [rt, ct] : root)
        d_cnt[rt] += ct;//, bug(rt);

    int res = -1;
    if (d_cnt.size() == 1 && (*d_cnt.begin()).x > 2)
        res = leaf;
    // bug(d_cnt.size());
    // bug((*d_cnt.begin()).x);
    if (d_cnt.size() > 1)
        res = leaf + 1 >> 1;
    cout << res << endl;
}

// void _()
// {
//     int n;
//     cin >> n;
//     vector<int> in(n + 1);
//     vector<vector<int>> e(n + 1);
//     for (int i = 1; i < n; i++)
//     {
//         int u, v;
//         cin >> u >> v;
//         e[u].push_back(v);
//         e[v].push_back(u);
//         in[u]++;
//         in[v]++;
//     }

//     int leaf = 0;
//     int has_3 = 0, cnt_2 = 0, cnt_1 = 0;
//     vector<int> vis(n + 1), d(n + 1, 1e18);
//     queue<int> q;
//     d[1] = 0;
//     q.push(1);
//     while (q.size())
//     {
//         int u = q.front();
//         q.pop();
//         if (vis[u])
//             continue;
//         vis[u] = 1;
//         for (auto v : e[u])
//         {
//             d[v] = min(d[v], d[u] + 1);
//             q.push(v);
//         }
//     }
//     map<int, int> root;
//     for (int i = 2; i <= n; i++)
//         if (in[i] == 1)
//         {
//             leaf++;
//             if (d[i] >= 3)
//                 has_3 = 1;
//             if (d[i] == 2)
//                 cnt_2++;
//             if (d[i] == 1)
//                 cnt_1++;
//             root[e[i][0]]++;
//         }

//     int ct_2 = 0, ct_1 = leaf - 2 * ct_2;
//     for (auto [x, ct] : root)
//         if (ct == 2)
//             ct_2++;
//     // int ans = ct_1 >= 2 * ct_2 ? 2 * ct_2 + (ct_1 - 2 * ct_2) / 2 + (ct_1 - 2 * ct_2) & 1
//     // : ct_1 + 2 * ct_2 - ct_1;
//     int ans = 0;
//     if (ct_2 & 1)
//         ans = ct_2 - 1, ct_2 = 1;
//     else
//         ans = ct_2;
//     if (ct_2 && ct_1)
//         ans++, ct_1--;
//     if (ct_2 && ct_1)
//         ans++, ct_2 = 0, ct_1--;
//     ans += ct_1 & 1 ? ct_1 / 2 + 1 : ct_1 / 2;

//     int res = -1;
//     if (has_3)
//         res = ans;
//     else if (cnt_2 && cnt_2 + cnt_1 > 1)
//         res = ans;
//     if (ct_2)
//         res = -1;
//     bug2(cnt_1, cnt_2);
//     // bug2(ct_1, ct_2);
//     cout << res << endl;
// }

// void _()
// {
//     int n;
//     cin >> n;
//     vector<int> in(n + 1);
//     vector<vector<int>> e(n + 1);
//     for (int i = 1; i < n; i++)
//     {
//         int u, v;
//         cin >> u >> v;
//         e[u].push_back(v);
//         e[v].push_back(u);
//         in[u]++;
//         in[v]++;
//     }

//     int leaf = 0;
//     int has_3 = 0, cnt_2 = 0, cnt_1 = 0;
//     vector<int> vis(n + 1), d(n + 1, 1e18);
//     queue<int> q;
//     d[1] = 0;
//     q.push(1);
//     while (q.size())
//     {
//         int u = q.front();
//         q.pop();
//         if (vis[u])
//             continue;
//         vis[u] = 1;
//         for (auto v : e[u])
//         {
//             d[v] = min(d[v], d[u] + 1);
//             q.push(v);
//         }
//     }

//     for (int i = 2; i <= n; i++)
//         if (in[i] == 1)
//         {
//             leaf++;
//             if (d[i] >= 3)
//                 has_3 = 1;
//             if (d[i] == 2)
//                 cnt_2++;
//             if (d[i] == 1)
//                 cnt_1++;
//         }
//     // int res = leaf;
//     // if (!has_3 && has_2)
//     //     res = -1;

//     int res = -1;
//     if (has_3)
//         res = leaf;
//     else if (cnt_2 && cnt_2 + cnt_1 > 1)
//         res = leaf;

//     cout << res << endl;
// }
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3588kb

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: 7ms
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
2
1
2
1
2
1
2
-1
2
2
1
1
2
1
1
1
-1
2
1
2
1
-1
1
1
2
1
1
-1
-1
2
1
1
1
-1
1
1
2
2
2
1
1
1
-1
1
1
1
-1
1
1
2
1
1
2
-1
-1
-1
2
2
2
-1
1
1
2
2
2
-1
1
2
-1
1
-1
-1
2
-1
-1
1
2
2
1
1
1
-1
1
1
1
-1
1
1
2
-1
1
1
2
-1
2
1
1
1
-1
2
-1
1
-1
-1
2
-1
2
1
2
2
-1
-1
1
1
1
-1
1
1
1
-1
1
1
2
1
1
1
1
...

result:

wrong answer 4th numbers differ - expected: '1', found: '-1'
English 繁體中文 简体中文

服务器时间: 2024-12-03 00:36:16 | 开源项目