QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#104099#392. Patrolfzj200753.333333 17ms7560kbC++142.5kb2023-05-08 16:42:192023-05-08 16:42:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-08 16:42:22]
  • 评测
  • 测评结果:53.333333
  • 用时:17ms
  • 内存:7560kb
  • [2023-05-08 16:42:19]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace IO{
	template<typename T>inline bool read(T &x){
		x=0;
		char ch=getchar();
		bool flag=0,ret=0;
		while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
		while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
		x=flag?-x:x;
        return ret;
	}
	template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
	    return read(a)&&read(args...);
	}
	template<typename T>void prt(T x){
		if(x>9) prt(x/10);
		putchar(x%10+'0');
	}
	template<typename T>inline void put(T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
	}
	template<typename T>inline void put(char ch,T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
		putchar(ch);
	}
	template<typename T,typename ...Args>inline void put(T a,Args ...args){
	    put(a);
		put(args...);
	}
	template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
	    put(ch,a);
		put(ch,args...);
	}
	inline void put(string s){
		for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
	}
	inline void put(const char* s){
		for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
	}
}
using namespace IO;
#define N 100005
#define inf 2000000
struct edge{
	int v,nxt,w;	
}e[N<<1];
int head[N],cnt=1,f[N],ans,res;
inline void add(int u,int v){
	e[++cnt]=(edge){v,head[u],1},head[u]=cnt;
}
inline void dfs(int x,int fa){
	int mx1=-inf,mx2=-inf;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,x);
		if(f[v]+e[i].w>mx1) mx2=mx1,mx1=f[v]+e[i].w;
		else if(f[v]+e[i].w>mx2) mx2=f[v]+e[i].w;
	}
	ans=max(ans,mx1+mx2),f[x]=max(mx1,0),ans=max(ans,f[x]);
}
inline void upd(int x,int fa){
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa) continue;
		if(f[x]==f[v]+e[i].w) return e[i].w=e[i^1].w=-1,upd(v,x),void();
	}
}
inline void update(int x,int fa){
	int mx1=-inf,mx2=-inf,ps1=-1,ps2=-1;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa) continue;
		update(v,x);
		if(f[v]+e[i].w>mx1) mx2=mx1,ps2=ps1,mx1=f[v]+e[i].w,ps1=v;
		else if(f[v]+e[i].w>mx2) mx2=f[v]+e[i].w,ps2=v;
	}
	if(mx1+mx2==ans)
		return upd(e[ps1].v,x),upd(e[ps2].v,x),e[ps1].w=e[ps1^1].w=e[ps2].w=e[ps2^1].w=-1,void();
	if(mx1==ans) return upd(e[ps1].v,x),e[ps1].w=e[ps1^1].w=-1,void();
}
int n,m;
int main(){
	read(n,m),ans=0;
	for(int i=1,u,v;i<n;i++) read(u,v),add(u,v),add(v,u); 
	dfs(1,0);
	if(m==1) return put('\n',n+n-2+1-ans),0;
	update(1,0),res=ans,ans=0,dfs(1,0);
	put('\n',n+n-2+2-ans-res);
	return 0;
}


详细

Test #1:

score: 3.33333
Accepted
time: 2ms
memory: 3324kb

input:

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

output:

15

result:

ok single line: '15'

Test #2:

score: 3.33333
Accepted
time: 2ms
memory: 3356kb

input:

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

output:

385

result:

ok single line: '385'

Test #3:

score: 3.33333
Accepted
time: 2ms
memory: 3540kb

input:

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

output:

1831

result:

ok single line: '1831'

Test #4:

score: 3.33333
Accepted
time: 0ms
memory: 3484kb

input:

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

output:

9965

result:

ok single line: '9965'

Test #5:

score: 3.33333
Accepted
time: 4ms
memory: 3980kb

input:

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

output:

39961

result:

ok single line: '39961'

Test #6:

score: 3.33333
Accepted
time: 17ms
memory: 6400kb

input:

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

output:

199955

result:

ok single line: '199955'

Test #7:

score: 3.33333
Accepted
time: 0ms
memory: 3700kb

input:

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

output:

18340

result:

ok single line: '18340'

Test #8:

score: 3.33333
Accepted
time: 1ms
memory: 6356kb

input:

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

output:

91709

result:

ok single line: '91709'

Test #9:

score: 3.33333
Accepted
time: 2ms
memory: 6932kb

input:

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

output:

183360

result:

ok single line: '183360'

Test #10:

score: 0
Wrong Answer
time: 0ms
memory: 3348kb

input:

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

output:

24

result:

wrong answer 1st lines differ - expected: '28', found: '24'

Test #11:

score: 0
Wrong Answer
time: 2ms
memory: 3344kb

input:

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

output:

177

result:

wrong answer 1st lines differ - expected: '175', found: '177'

Test #12:

score: 0
Wrong Answer
time: 0ms
memory: 3388kb

input:

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

output:

1951

result:

wrong answer 1st lines differ - expected: '1953', found: '1951'

Test #13:

score: 0
Wrong Answer
time: 0ms
memory: 3636kb

input:

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

output:

19933

result:

wrong answer 1st lines differ - expected: '19934', found: '19933'

Test #14:

score: 3.33333
Accepted
time: 3ms
memory: 3668kb

input:

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

output:

19930

result:

ok single line: '19930'

Test #15:

score: 3.33333
Accepted
time: 9ms
memory: 4888kb

input:

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

output:

99922

result:

ok single line: '99922'

Test #16:

score: 0
Wrong Answer
time: 11ms
memory: 6576kb

input:

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

output:

199908

result:

wrong answer 1st lines differ - expected: '199910', found: '199908'

Test #17:

score: 3.33333
Accepted
time: 2ms
memory: 3400kb

input:

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

output:

1798

result:

ok single line: '1798'

Test #18:

score: 3.33333
Accepted
time: 0ms
memory: 3524kb

input:

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

output:

3615

result:

ok single line: '3615'

Test #19:

score: 3.33333
Accepted
time: 2ms
memory: 5668kb

input:

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

output:

18240

result:

ok single line: '18240'

Test #20:

score: 0
Wrong Answer
time: 11ms
memory: 5360kb

input:

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

output:

83258

result:

wrong answer 1st lines differ - expected: '91573', found: '83258'

Test #21:

score: 0
Wrong Answer
time: 6ms
memory: 6612kb

input:

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

output:

133068

result:

wrong answer 1st lines differ - expected: '146479', found: '133068'

Test #22:

score: 0
Wrong Answer
time: 17ms
memory: 7560kb

input:

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

output:

166566

result:

wrong answer 1st lines differ - expected: '183232', found: '166566'

Test #23:

score: 0
Wrong Answer
time: 4ms
memory: 3656kb

input:

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

output:

19487

result:

wrong answer 1st lines differ - expected: '19495', found: '19487'

Test #24:

score: 0
Wrong Answer
time: 1ms
memory: 3672kb

input:

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

output:

18901

result:

wrong answer 1st lines differ - expected: '18913', found: '18901'

Test #25:

score: 0
Wrong Answer
time: 4ms
memory: 4904kb

input:

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

output:

98130

result:

wrong answer 1st lines differ - expected: '98142', found: '98130'

Test #26:

score: 0
Wrong Answer
time: 4ms
memory: 5892kb

input:

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

output:

99954

result:

wrong answer 1st lines differ - expected: '99957', found: '99954'

Test #27:

score: 3.33333
Accepted
time: 5ms
memory: 5860kb

input:

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

output:

99970

result:

ok single line: '99970'

Test #28:

score: 3.33333
Accepted
time: 11ms
memory: 6412kb

input:

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

output:

199971

result:

ok single line: '199971'

Test #29:

score: 0
Wrong Answer
time: 13ms
memory: 6412kb

input:

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

output:

199947

result:

wrong answer 1st lines differ - expected: '199949', found: '199947'

Test #30:

score: 0
Wrong Answer
time: 11ms
memory: 6400kb

input:

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

output:

199973

result:

wrong answer 1st lines differ - expected: '199976', found: '199973'