QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#657572#6307. Chase Game 2Fluoresce#WA 23ms6944kbC++201.7kb2024-10-19 15:00:102024-10-19 15:00:11

Judging History

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

  • [2024-10-19 15:00:11]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:6944kb
  • [2024-10-19 15:00:10]
  • 提交

answer

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
typedef long long ll;
typedef long double ld;
#define debug(a) cout<<a<<'\n'
#define Pll pair<ll,ll>
#define PII pair<int,int>
#define ft first
#define sd second
#define vec vector
#define pushk push_back
#define ump unordered_map
#define pl p<<1
#define pr p<<1|1
using namespace std;
const int N = 2e5 + 10, M = 1e4 + 10, mod = 1e9 + 7;
const ll inf = 1e18;
const ld eps = 1e-13;
int mov[4][2] = { {0,1},{1,0},{-1,0},{0,-1} }, dx, dy, _ = 1, __ = 1;
void bout(bool f) {
	if (f)cout << "Yes\n";
	else cout << "No\n";
}
ll n, m, k;
int h[N],e[N<<1],ne[N<<1],idx;

void link(int x,int y){
	e[++idx]=y;
	ne[idx]=h[x];
	h[x]=idx;
}
map<int,int>mp;
int sum=0,cnt=0,dep;
bool vis[N];

bool dfs(int u,int dp){
	vis[u]=1;
	int d=0;
	bool f=1;
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(!vis[v]){
			if(dfs(v,dp+1))
			++d;
			f=0;
		}
	}
	vis[u]=0;
	if(d){
		++cnt;
		++mp[d];
	}
	sum+=d;
	dep=max(dep,dp);
	return f;
}
void ini() {
}
void solve() {
	cin>>n;
	memset(h,-1,4*(n+3));idx=0;
	mp.clear();
	sum=0;cnt=0;
	int x,y,rt=1;
	for(int i=1;i<n;++i){
		cin>>x>>y;
		if(h[x])rt=x;
		else if(h[y])rt=y;
		link(x,y);
		link(y,x);
	}
	dep=1;
	dfs(rt,1);
	if(cnt>1||dep>3)cout<<max((*mp.rbegin()).ft,(sum+1)/2)<<'\n';
	else cout<<"-1\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	streambuf* cinbackup = cin.rdbuf(), * coutbackup = cout.rdbuf();
	ifstream fin("in.txt");
	ofstream fout("out.txt");
	cin.rdbuf(fin.rdbuf());
	cout.rdbuf(fout.rdbuf());
#endif
	cin >> _;
	__ = _;
	ini();
	while (_--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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: 0
Accepted
time: 5ms
memory: 5724kb

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:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 8ms
memory: 5732kb

input:

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

output:

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

result:

ok 10000 numbers

Test #5:

score: 0
Accepted
time: 17ms
memory: 5732kb

input:

10000
20
1 2
1 3
1 4
2 5
4 6
6 7
2 8
4 9
7 10
6 11
4 12
6 13
13 14
10 15
8 16
11 17
5 18
15 19
10 20
19
1 2
1 3
2 4
3 5
4 6
1 7
1 8
2 9
4 10
10 11
8 12
2 13
4 14
1 15
4 16
4 17
14 18
3 19
20
1 2
1 3
1 4
1 5
1 6
5 7
3 8
5 9
1 10
8 11
8 12
2 13
7 14
4 15
2 16
12 17
14 18
18 19
1 20
19
1 2
1 3
3 4
2 5
...

output:

5
6
5
5
5
4
5
6
3
6
5
4
5
6
5
6
5
5
5
5
5
4
5
5
5
6
6
5
6
4
5
5
6
4
5
5
4
5
3
6
5
5
6
5
5
4
5
3
6
6
5
5
6
4
6
5
5
5
6
5
5
5
4
6
4
5
5
5
4
5
5
5
6
7
5
5
6
6
4
6
5
5
5
5
6
6
5
6
6
6
4
5
6
4
5
4
4
5
5
6
5
5
5
7
5
5
5
5
4
4
6
4
6
4
5
4
4
6
4
5
5
5
4
5
5
5
6
5
5
6
5
5
3
4
6
4
4
5
5
5
4
4
6
5
5
5
5
6
5
6
...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 12ms
memory: 5716kb

input:

4000
45
1 2
2 3
2 4
4 5
2 6
2 7
7 8
8 9
1 10
1 11
3 12
11 13
8 14
13 15
8 16
16 17
12 18
11 19
6 20
3 21
6 22
15 23
13 24
2 25
22 26
8 27
20 28
1 29
22 30
9 31
12 32
7 33
31 34
31 35
25 36
19 37
34 38
4 39
14 40
40 41
3 42
42 43
26 44
21 45
46
1 2
2 3
2 4
3 5
4 6
2 7
6 8
1 9
1 10
9 11
4 12
8 13
6 14...

output:

11
11
12
14
10
11
14
11
14
12
11
12
12
11
13
12
12
13
12
13
10
10
13
12
11
11
12
11
12
12
11
12
13
10
14
12
11
9
11
12
12
11
13
12
14
13
10
9
12
13
12
12
12
14
12
11
13
11
13
13
14
11
13
13
13
11
11
13
11
13
13
11
11
12
12
11
11
11
13
12
13
11
13
12
12
13
13
12
13
14
11
12
11
12
11
12
12
13
14
12
12...

result:

ok 4000 numbers

Test #7:

score: 0
Accepted
time: 16ms
memory: 5780kb

input:

2000
94
1 2
2 3
3 4
4 5
1 6
3 7
5 8
4 9
3 10
7 11
8 12
12 13
4 14
12 15
12 16
5 17
13 18
6 19
16 20
14 21
17 22
7 23
10 24
1 25
22 26
18 27
23 28
19 29
17 30
13 31
11 32
8 33
3 34
21 35
23 36
35 37
28 38
6 39
15 40
28 41
26 42
36 43
1 44
37 45
1 46
30 47
7 48
37 49
3 50
23 51
47 52
33 53
1 54
34 55
...

output:

25
23
22
23
25
23
24
25
21
21
24
24
23
21
25
25
25
23
25
24
23
22
26
26
23
24
25
26
24
23
22
25
25
24
23
22
24
22
24
23
24
26
25
22
22
22
25
21
25
24
26
26
25
24
25
24
24
25
23
24
23
24
21
23
24
25
22
25
24
25
22
25
22
23
24
26
25
27
23
24
25
25
23
23
24
23
23
25
25
27
22
21
23
28
27
23
25
26
23
23
...

result:

ok 2000 numbers

Test #8:

score: 0
Accepted
time: 17ms
memory: 5788kb

input:

200
959
1 2
1 3
2 4
2 5
3 6
1 7
5 8
7 9
1 10
2 11
2 12
6 13
9 14
14 15
3 16
6 17
12 18
5 19
7 20
12 21
18 22
1 23
8 24
11 25
2 26
19 27
4 28
21 29
15 30
22 31
21 32
32 33
15 34
22 35
11 36
22 37
34 38
18 39
7 40
13 41
29 42
40 43
34 44
28 45
37 46
10 47
8 48
12 49
2 50
17 51
39 52
35 53
16 54
31 55
...

output:

236
231
238
231
227
235
241
230
238
230
236
237
224
237
241
235
244
242
245
243
234
236
239
231
228
227
228
238
243
234
238
255
253
230
239
254
226
233
230
242
235
240
235
242
229
249
246
249
242
243
234
237
235
227
249
240
244
233
234
244
241
233
234
225
237
242
239
242
232
248
233
234
220
222
227
...

result:

ok 200 numbers

Test #9:

score: 0
Accepted
time: 19ms
memory: 5900kb

input:

20
9597
1 2
1 3
1 4
4 5
3 6
2 7
2 8
2 9
5 10
7 11
2 12
9 13
2 14
1 15
5 16
11 17
16 18
2 19
11 20
9 21
12 22
16 23
10 24
21 25
12 26
9 27
6 28
1 29
13 30
15 31
18 32
6 33
26 34
21 35
16 36
19 37
30 38
36 39
30 40
27 41
14 42
40 43
32 44
2 45
34 46
4 47
26 48
32 49
24 50
17 51
27 52
36 53
44 54
7 55
...

output:

2403
2490
2391
2263
2356
2482
2384
2469
2386
2265
2283
2342
2381
2382
2261
2353
2287
2499
2458
2426

result:

ok 20 numbers

Test #10:

score: 0
Accepted
time: 23ms
memory: 6944kb

input:

2
92316
1 2
2 3
1 4
3 5
2 6
1 7
6 8
8 9
4 10
5 11
4 12
8 13
5 14
7 15
14 16
15 17
4 18
12 19
3 20
1 21
4 22
8 23
16 24
20 25
15 26
15 27
7 28
7 29
15 30
27 31
18 32
14 33
28 34
22 35
11 36
16 37
30 38
30 39
5 40
32 41
16 42
12 43
26 44
16 45
38 46
34 47
35 48
41 49
22 50
18 51
7 52
5 53
1 54
37 55
1...

output:

22980
24011

result:

ok 2 number(s): "22980 24011"

Test #11:

score: -100
Wrong Answer
time: 5ms
memory: 5724kb

input:

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

output:

3
4
2
2
4
3
3
6
3
4
-1
4
5
4
2
4
2
5
4
4
3
3
1
5
5
4
3
5
6
5
-1
3
5
-1
-1
4
-1
4
3
3
3
2
-1
-1
5
3
-1
3
5
5
-1
5
4
4
-1
3
2
3
3
2
2
5
-1
3
-1
4
3
-1
4
4
4
3
3
4
4
3
2
-1
-1
3
2
5
4
2
-1
4
2
3
-1
3
2
-1
6
4
2
5
3
4
4
2
3
2
2
-1
-1
5
4
3
3
-1
-1
-1
2
3
4
5
-1
5
3
-1
5
-1
2
3
6
6
4
2
4
2
6
-1
5
5
3
6
2...

result:

wrong answer 1st numbers differ - expected: '4', found: '3'