QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358731#6307. Chase Game 2Djangle162857WA 10ms3628kbC++201.5kb2024-03-19 23:15:202024-03-19 23:15:20

Judging History

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

  • [2024-03-19 23:15:20]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:3628kb
  • [2024-03-19 23:15:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " == " << x << endl
#define el '\n'
typedef long long ll;
const int mod = 1000000007;
const int inf = 2147483647;
const int N = 200020;
void solve()
{
	int n, m;
	cin >> n;
	vector<vector<int>> edge(n + 1);
	vector<int> f(n + 1, 0), dep(n + 1, 0), inp(n + 1, 0), vis(n + 1, 0);
	for (int i = 1, x, y; i < n; i++) {
		cin >> x >> y;
		edge[x].push_back(y);
		edge[y].push_back(x);
		inp[x]++, inp[y]++;
	}
	int rt = 0;
	function<void(int, int)> dfs = [&](int x, int fa) {
		f[x] = fa;
		dep[x] = dep[fa] + 1;
		for (int to : edge[x]) {
			if (to == fa)
				continue;
			dfs(to, x);
		}
		if (dep[x] > dep[rt])
			rt = x;
	};
	dfs(1, 0);
	int st = rt;
	dfs(rt, 0);
	vector<int> c;
	do {
		c.push_back(rt);
		rt = f[rt];
	} while (rt);
	int cnt = 0, leaf = 0;
	for (int i = 1; i <= n; i++) {
		if (inp[i] == 1)
			leaf++;
		if (inp[i] > 1)
			cnt++;
	}
	if (cnt <= 1) {
		cout << "-1" << el;
		return;
	}
	int mx = 1, tot = 0;
	for (int i = 1; i < c.size() - 1; i++) {
		if (i == 1 || i == c.size() - 2) {
			mx = max(mx, inp[c[i]] - 1);
		}
		else {
			mx = max(mx, inp[c[i]] - 2);
		}
		vis[c[i]] = 1;
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			mx = max(mx, inp[i] - 1);
		}
	}
	cout << max(mx, (leaf + 1) >> 1) << el;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

詳細信息

Test #1:

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

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: 7ms
memory: 3628kb

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: 10ms
memory: 3572kb

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
4
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
4
3
3
2
2
3
2
2
2
3
3
2
3
3
2
4
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
5
3
3
2
2
3
2
3
4
2
5
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 170th numbers differ - expected: '3', found: '4'