QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#100020#6307. Chase Game 2Social_Pointer#WA 49ms5408kbC++201.3kb2023-04-24 14:10:522023-04-24 14:10:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-24 14:10:54]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:5408kb
  • [2023-04-24 14:10:52]
  • 提交

answer

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>

using namespace std;
const int N = 2e5 + 10, M = 2 * N, INF = 0x3f3f3f3f;
const int mod = 998244353;
int n, m, a[N];
int h[N], e[M], ne[M], w[M], idx;
int depth[N], sz[N], son[N], d[N];
int ans = 1;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int fa) {
    depth[u] = depth[fa] + 1;
    for(int i = h[u]; ~i ; i = ne[i]) {
        int j = e[i];
        if(j == fa) continue;
        dfs(j, u);
    }
}

signed main () {
    int T = 1;
    cin >> T;
    while (T-- ) {
        cin >> n;
        for (int i = 1; i <= n; i++ )
            h[i] = -1, d[i] = 0;
        idx = 0;
        for(int i = 1; i < n ; i ++ ) {
            int a, b;
            cin >> a >> b;
            add(a, b), add(b, a);
            d[a]++, d[b]++ ;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++ ) 
            if (d[i] == 1) ans++ ;
        dfs(1, 0);
        int root = 1;
        for (int i = 1; i <= n; i++ )
            if (depth[root] < depth[i]) root = i;
        dfs(root, 0);
        int mx = 0;
        for (int i = 1; i <= n; i++ ) 
            mx = max(mx, depth[i]);
        if (mx <= 3) cout << -1 << endl;
        else cout << (ans + 1) / 2 << endl;
    }
}

详细

Test #1:

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

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: 0
Accepted
time: 27ms
memory: 5364kb

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

result:

ok 10000 numbers

Test #3:

score: -100
Wrong Answer
time: 49ms
memory: 5408kb

input:

10000
9
1 2
2 3
3 4
4 5
1 6
6 7
5 8
7 9
9
1 2
2 3
2 4
1 5
2 6
4 7
6 8
1 9
9
1 2
2 3
1 4
4 5
5 6
4 7
2 8
1 9
10
1 2
2 3
1 4
3 5
3 6
2 7
6 8
6 9
6 10
10
1 2
1 3
3 4
2 5
1 6
5 7
4 8
2 9
7 10
10
1 2
2 3
2 4
1 5
3 6
6 7
5 8
4 9
9 10
9
1 2
2 3
2 4
1 5
3 6
2 7
1 8
2 9
9
1 2
1 3
2 4
1 5
3 6
3 7
7 8
8 9
10
1...

output:

1
3
3
3
2
2
3
2
3
2
3
2
3
2
3
3
3
2
3
2
3
2
3
3
2
2
3
3
3
3
3
3
2
3
3
3
3
3
3
3
2
3
3
3
3
3
2
3
3
3
3
3
3
2
3
2
3
2
2
3
3
4
3
3
3
3
2
2
3
2
2
2
3
3
2
3
3
2
3
3
3
3
2
3
2
2
3
3
3
3
2
3
3
2
3
3
3
3
3
2
3
2
2
3
3
3
3
2
2
3
2
3
4
2
4
3
2
3
3
2
3
2
3
3
3
3
2
2
3
3
3
2
3
3
3
3
3
3
2
3
3
2
2
4
3
3
3
3
2
3
...

result:

wrong answer 37th numbers differ - expected: '4', found: '3'