QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#724221#2644. Cats or DogsShumomo38 14ms4180kbC++14994b2024-11-08 11:02:062024-11-08 11:02:15

Judging History

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

  • [2024-11-08 11:02:15]
  • 评测
  • 测评结果：38
  • 用时：14ms
  • 内存：4180kb
查看
  • [2024-11-08 11:02:06]
  • 提交

answer

#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
int h[100009],ver[200009],nxt[200009],tot,f[100009][4],g[100009];
void dfs(int x,int fa){
	f[x][0]=f[x][1]=f[x][2]=0;
	for(int i=h[x];i;i=nxt[i]){
		int y=ver[i];
		if(y!=fa){
			dfs(y,x);
			f[x][0]+=min(f[y][0],min(f[y][1],f[y][2])+1);
			f[x][1]+=min(min(f[y][0],f[y][1]),f[y][2]+1);
			f[x][2]+=min(min(f[y][0],f[y][2]),f[y][1]+1);
		}
	}
	if(g[x]==1)f[x][0]=f[x][2]=0x3f3f3f3f;
	if(g[x]==2)f[x][0]=f[x][1]=0x3f3f3f3f;
}
void initialize(int n,vector<int> A,vector<int> B) {
	for(int i=0;i<n-1;i++){
		tot++;
		nxt[tot]=h[A[i]];
		ver[tot]=B[i];
		h[A[i]]=tot;
		tot++;
		nxt[tot]=h[B[i]];
		ver[tot]=A[i];
		h[B[i]]=tot;
	}
}

int cat(int v){
	g[v]=1;
	dfs(1,0);
	return min(f[1][0],min(f[1][1],f[1][2]));
}

int dog(int v) {
	g[v]=2;
	dfs(1,0);
	return min(f[1][0],min(f[1][1],f[1][2]));
}

int neighbor(int v) {
	g[v]=0;
	dfs(1,0);
	return min(f[1][0],min(f[1][1],f[1][2]));
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 8
Accepted

Test #1:

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

input:

2
2 1
75
1 2
1 1
3 1
3 2
1 1
2 2
3 1
3 2
2 2
3 2
1 1
3 1
1 2
2 1
3 2
2 2
3 2
1 2
3 1
1 1
3 2
3 1
1 2
3 2
2 1
2 2
3 2
3 1
2 1
1 2
3 1
1 1
3 2
3 1
1 2
3 2
2 1
3 1
1 1
1 2
3 1
3 2
2 1
1 2
3 1
2 1
3 2
2 2
3 1
2 1
3 2
2 2
3 2
2 2
3 1
3 2
1 1
3 1
2 2
1 1
3 1
1 1
3 2
2 2
3 2
3 1
2 2
2 1
3 1
2 1
3 2
1 2
3 1...

output:

0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
1
0
1
0

result:

ok 75 lines

Test #2:

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

input:

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

output:

0
0
1
1
2
4
2
2
2
2
0
2
2
2
3
1
1
1
1
1
1
2
2
3
3
1
1
2
1
1
0
1

result:

ok 32 lines

Test #3:

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

input:

15
2 15
7 14
9 1
15 11
3 14
2 5
13 3
3 2
12 11
6 14
8 10
8 5
13 1
7 4
43
1 14
1 11
1 12
1 6
2 1
2 7
3 14
3 6
2 9
3 9
2 2
3 2
2 8
2 2
3 7
2 3
3 3
2 5
1 6
2 3
3 11
1 13
1 9
1 4
2 11
3 1
3 9
3 11
3 5
3 13
3 4
2 7
3 3
1 11
1 4
3 4
2 13
3 2
2 15
1 9
1 4
3 9
3 13

output:

0
0
0
0
1
2
2
1
1
1
1
1
1
1
1
1
1
1
2
2
2
4
5
5
5
3
3
3
3
2
2
2
2
2
3
2
2
2
2
3
4
3
3

result:

ok 43 lines

Test #4:

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

input:

9
9 2
5 7
1 7
2 1
9 3
1 4
6 7
6 8
100
2 6
2 8
2 7
1 9
2 2
3 6
2 5
1 1
2 6
3 8
1 4
3 9
2 8
3 8
3 1
2 9
3 5
1 8
3 9
3 4
2 5
2 3
3 6
2 4
3 2
3 5
3 7
3 3
1 1
2 9
2 7
2 3
3 9
2 5
2 2
3 7
2 9
3 1
3 5
1 5
3 5
3 2
2 6
1 7
3 8
3 9
3 7
3 3
3 6
2 5
1 9
3 9
1 9
1 8
3 9
2 1
1 2
3 5
1 7
3 8
2 9
3 2
3 7
2 7
3 9
1 ...

output:

0
0
0
1
1
1
1
3
3
3
3
2
2
2
1
1
1
2
2
1
1
1
1
1
1
1
1
1
1
2
4
4
4
4
4
3
3
1
1
1
1
1
1
3
2
2
0
0
0
0
1
0
1
2
1
1
2
2
2
2
3
1
0
0
0
1
1
1
4
4
4
2
2
2
1
0
0
1
1
1
0
0
0
1
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0

result:

ok 100 lines

Test #5:

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

input:

11
4 11
1 7
10 11
7 4
5 3
1 8
7 2
1 9
5 8
6 5
91
2 8
1 11
3 8
2 7
2 8
2 6
1 5
1 9
2 10
3 10
2 1
3 6
2 10
3 7
1 3
1 7
3 7
3 10
3 5
3 1
3 8
1 1
2 8
1 6
3 3
1 7
3 7
2 7
3 8
2 5
3 9
2 10
1 2
3 5
2 8
3 10
2 9
1 3
3 6
1 6
3 7
1 7
3 2
2 10
3 9
3 8
1 2
1 8
1 4
3 10
3 8
3 7
2 5
2 7
3 3
3 7
2 8
3 1
3 2
2 2
2 ...

output:

0
1
0
1
1
1
3
4
5
4
4
3
4
4
4
4
4
3
3
2
0
0
2
2
2
2
2
4
2
4
4
5
6
4
6
5
6
6
6
6
3
3
3
4
3
1
1
1
1
0
0
0
3
6
5
2
2
2
2
2
2
2
3
2
2
2
2
1
1
1
1
1
1
1
3
3
2
1
1
1
0
0
0
0
1
2
2
2
2
2
2

result:

ok 91 lines

Test #6:

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

input:

15
11 1
8 1
9 11
8 12
14 12
13 15
7 13
4 15
3 4
5 9
15 2
4 12
15 10
6 11
100
1 1
2 11
2 7
3 7
3 1
1 9
2 5
1 6
2 12
2 13
2 1
3 13
3 1
3 9
2 14
1 9
2 7
2 13
3 14
3 5
2 1
3 9
1 3
1 10
2 9
3 11
3 3
3 1
2 2
3 12
1 5
1 15
1 4
3 10
3 7
3 9
2 1
1 14
3 13
1 10
3 15
3 10
1 8
2 12
3 5
3 8
2 15
3 1
1 5
3 5
3 12...

output:

0
1
2
1
0
1
2
3
3
3
3
3
3
1
1
3
3
3
3
2
2
1
2
3
3
3
2
2
2
2
3
4
4
4
4
2
4
4
3
3
3
3
3
6
6
4
4
4
4
4
1
1
1
3
3
2
3
3
3
3
3
3
3
3
4
4
4
6
6
4
6
4
4
3
3
4
4
4
3
2
2
1
2
3
3
2
3
5
5
6
6
7
6
6
7
6
7
6
6
6

result:

ok 100 lines

Test #7:

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

input:

15
7 1
9 11
10 1
9 13
15 11
10 4
10 6
6 13
4 2
5 15
12 9
14 11
3 11
8 11
100
1 12
1 15
1 8
1 13
1 10
3 13
1 11
1 1
1 13
3 8
2 4
1 6
3 12
3 6
1 14
3 13
3 10
3 1
1 13
1 8
2 6
3 6
1 9
1 6
2 1
3 13
1 2
3 8
3 14
3 1
1 12
1 5
3 4
3 12
1 10
3 10
3 9
3 6
1 3
1 9
3 11
2 13
2 10
2 1
3 15
2 15
3 10
1 6
2 10
3 ...

output:

0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
0
0
0
0
0
0
0
0
0
2
2
2
2
4
4
5
6
5
3
3
3
3
3
3
3
3
3
3
4
2
4
5
5
5
5
5
5
5
4
2
2
3
3
5
6
6
6
6
6
6
5
5
4
5
3
2
2
2
2
1
1
1
1
1
2
2
3
3

result:

ok 100 lines

Test #8:

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

input:

15
4 7
13 2
8 15
5 11
14 4
5 9
15 2
14 12
6 14
11 10
11 8
3 13
12 9
1 12
100
1 10
2 11
1 7
2 5
1 2
1 14
1 15
3 5
3 10
1 9
3 9
1 1
2 3
1 13
1 5
3 5
2 4
2 6
3 15
2 12
1 10
3 1
3 4
2 4
3 7
3 3
3 4
1 8
2 7
3 14
3 12
2 14
2 1
2 12
2 9
3 14
2 15
3 11
3 9
3 13
2 9
1 14
3 15
3 8
2 4
3 2
1 2
3 1
3 2
3 10
3 1...

output:

0
1
2
2
3
3
3
3
2
2
2
2
3
3
3
3
5
6
6
7
8
7
5
7
6
5
4
4
5
2
2
2
2
2
2
2
4
3
3
3
3
6
4
4
4
4
4
4
4
3
0
1
1
1
1
1
1
1
1
1
2
1
4
5
2
2
4
4
2
3
5
5
5
5
5
3
3
3
2
3
3
4
3
3
4
5
5
5
3
5
5
4
4
4
2
2
2
2
3
3

result:

ok 100 lines

Test #9:

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

input:

15
11 1
11 9
14 5
14 7
12 6
9 7
10 14
13 5
6 2
4 13
4 3
3 6
6 8
15 3
100
1 3
2 13
2 4
1 14
1 15
3 14
1 11
2 9
2 5
3 4
1 10
3 11
1 7
3 7
1 2
3 3
3 13
3 9
1 1
1 11
1 8
2 9
1 13
3 11
1 12
3 12
1 11
3 1
2 3
3 9
1 4
3 13
2 7
3 8
3 4
3 5
3 3
1 9
2 3
3 2
1 12
1 6
3 10
2 13
3 9
3 6
3 13
1 4
2 8
3 3
1 13
3 4...

output:

0
1
1
2
2
1
2
2
2
2
3
2
3
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
6
5
5
5
6
6
4
4
2
2
4
3
4
4
3
3
3
3
3
5
5
3
3
3
3
3
3
3
4
4
4
3
3
2
2
2
2
2
2
2
2
3
3
3
4
4
4
7
4
4
4
4
4
4
3
2
3
5
5
5
5
5
5
5
5
4
3
3
3
3
3
2

result:

ok 100 lines

Test #10:

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

input:

15
14 12
4 1
8 7
9 5
3 7
2 12
1 13
2 10
9 12
7 9
7 4
6 10
11 3
15 13
100
1 5
1 13
2 10
2 3
3 3
2 14
1 2
1 9
3 9
3 5
3 2
3 14
2 9
3 13
1 15
3 9
2 11
1 4
3 4
1 7
2 13
2 14
3 11
3 10
3 14
1 3
3 13
2 9
3 9
3 7
1 6
1 10
3 15
2 15
2 5
1 2
3 6
3 3
3 2
2 13
1 6
2 14
2 2
3 13
3 6
3 2
1 12
2 4
3 4
2 11
3 10
2...

output:

0
0
1
2
1
1
2
2
2
2
1
1
1
0
1
1
1
1
1
2
4
4
3
3
2
2
0
1
0
0
0
0
0
1
2
2
2
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
3
5
5
4
2
2
1
1
1
1
1
2
2
1
2
2
5
4
4
4
5
5
6
6
4
4
4
4
1
1
1
1
1
1
1
1
2
3
5
3
4
3
4
2
2
2
2
2

result:

ok 100 lines

Test #11:

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

input:

15
13 11
11 8
12 8
12 5
5 6
6 14
7 14
7 9
4 9
4 3
10 3
15 10
15 1
2 1
64
1 9
1 11
2 10
1 14
3 11
2 12
2 2
1 5
2 8
2 7
3 14
3 7
1 15
2 11
2 14
3 10
1 3
3 2
2 2
3 3
3 9
2 9
3 2
3 11
1 2
3 2
1 4
1 6
2 1
2 10
1 11
3 1
1 2
2 7
3 8
3 14
3 9
3 4
1 8
3 2
3 5
1 13
3 15
3 10
3 6
3 11
2 9
3 13
3 9
2 9
1 11
3 7...

output:

0
0
1
1
1
2
2
2
2
4
4
2
4
4
6
4
4
3
4
4
4
4
3
3
3
3
3
3
4
6
7
6
6
6
6
6
6
4
4
4
4
4
3
3
1
1
1
1
1
1
1
1
2
2
4
4
3
1
3
3
3
3
3
5

result:

ok 64 lines

Test #12:

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

input:

7
3 4
1 4
5 1
7 5
7 2
6 2
1
2 2

output:

0

result:

ok single line: '0'

Test #13:

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

input:

2
1 2
47
1 2
3 2
1 2
1 1
3 2
2 2
3 1
1 1
3 2
3 1
1 1
3 1
1 1
3 1
2 1
3 1
1 2
2 1
3 2
1 2
3 2
1 2
3 2
1 2
3 1
2 1
3 1
3 2
1 2
1 1
3 2
1 2
3 1
3 2
2 1
1 2
3 1
3 2
1 1
2 2
3 1
2 1
3 2
2 2
3 2
3 1
2 1

output:

0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0

result:

ok 47 lines

Test #14:

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

input:

2
2 1
64
1 1
2 2
3 2
2 2
3 1
1 1
3 2
1 2
3 2
3 1
2 2
3 2
2 2
3 2
1 1
1 2
3 1
2 1
3 2
3 1
2 2
3 2
1 2
3 2
2 2
3 2
2 2
1 1
3 2
3 1
2 2
1 1
3 2
3 1
2 2
1 1
3 2
1 2
3 1
2 1
3 2
2 2
3 2
3 1
1 2
3 2
1 1
1 2
3 1
2 1
3 1
2 1
3 2
2 2
3 1
1 1
3 2
1 2
3 1
3 2
2 2
3 2
1 2
3 2

output:

0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0

result:

ok 64 lines

Test #15:

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

input:

3
2 1
1 3
55
2 2
1 3
3 2
2 1
3 1
2 2
3 2
1 1
2 2
3 1
3 3
2 1
3 2
2 3
3 1
2 1
3 3
1 2
1 3
3 2
3 3
2 2
3 1
3 2
1 1
3 1
2 3
3 3
2 1
3 1
2 3
3 3
1 2
3 2
2 2
1 1
3 1
1 1
2 3
3 3
1 3
3 2
3 3
3 1
1 1
1 3
2 2
3 2
1 2
3 2
3 1
3 3
1 3
1 1
3 1

output:

0
1
0
1
0
1
0
0
1
1
0
0
0
0
0
0
0
1
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
2
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0

result:

ok 55 lines

Test #16:

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

input:

14
14 13
13 11
5 13
13 4
3 13
10 13
13 7
13 6
12 13
1 13
8 13
13 9
13 2
97
2 9
1 5
1 2
2 4
2 12
3 4
3 5
1 11
1 5
2 6
2 14
3 14
3 2
3 6
2 6
3 9
3 5
1 1
2 10
3 1
1 13
3 6
1 8
3 13
1 2
1 14
3 12
2 4
2 13
2 3
1 1
2 12
3 10
3 4
2 7
3 1
3 12
3 3
1 3
2 10
2 1
1 4
2 5
3 3
2 9
1 6
3 4
2 4
3 4
3 10
3 14
1 4
2...

output:

0
1
1
2
2
2
1
2
2
3
3
3
2
2
2
2
1
2
2
1
3
2
2
2
2
2
1
2
4
4
5
5
5
5
5
4
4
4
5
5
5
6
6
5
5
6
5
5
5
5
4
5
5
4
4
4
3
2
2
2
2
1
2
3
3
2
2
2
1
1
2
3
3
4
3
3
3
4
4
5
4
4
3
3
3
3
3
3
3
2
1
2
2
1
1
1
0

result:

ok 97 lines

Subtask #2:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #17:

score: 30
Accepted
time: 5ms
memory: 4104kb

input:

740
717 38
630 627
569 28
124 227
518 170
590 737
104 464
108 665
489 99
713 3
374 54
21 280
250 436
400 128
558 687
286 521
327 687
101 675
516 713
141 91
30 613
419 225
218 505
274 545
254 567
609 525
3 231
528 509
612 690
262 105
275 68
192 23
383 631
365 127
372 662
248 182
143 495
130 415
249 3...

output:

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

result:

ok 747 lines

Test #18:

score: 30
Accepted
time: 5ms
memory: 3836kb

input:

931
627 537
349 208
170 929
859 502
311 847
576 917
73 266
550 460
924 311
107 638
440 176
866 795
536 615
844 605
325 775
27 276
2 663
294 123
608 357
857 880
678 391
241 725
492 366
829 501
123 921
633 176
605 746
924 910
526 370
193 107
158 166
142 536
817 171
440 422
267 390
664 703
441 687
762 ...

output:

0
1
1
1
2
2
2
2
3
4
4
4
4
4
4
4
6
6
6
7
7
7
7
8
8
9
9
9
9
9
10
10
10
10
11
11
11
12
12
12
12
14
14
14
14
14
14
16
17
17
17
17
18
18
18
18
18
18
18
18
18
18
19
19
20
21
22
23
23
24
24
24
24
25
24
24
24
25
26
25
25
25
25
25
25
25
25
25
25
25
25
25
26
26
26
26
27
27
27
27
25
25
26
26
26
27
27
27
27
27
...

result:

ok 730 lines

Test #19:

score: 30
Accepted
time: 3ms
memory: 3912kb

input:

784
391 610
341 483
415 48
156 42
337 734
339 95
110 4
388 420
408 656
284 447
552 112
781 108
761 603
188 121
267 633
595 169
129 470
112 194
275 195
197 174
477 245
118 766
158 324
670 562
10 429
634 450
649 465
316 424
149 52
25 612
240 639
508 535
348 78
337 120
689 450
538 178
234 240
206 516
7...

output:

0
0
0
0
1
1
1
1
1
1
1
2
2
2
2
2
2
3
4
4
5
7
7
7
9
10
11
12
13
13
13
13
13
13
13
13
14
15
15
16
17
18
18
20
20
20
20
20
21
20
20
20
20
21
21
22
23
23
24
25
24
24
24
24
24
25
26
26
26
27
27
27
27
28
28
28
28
29
29
30
30
31
33
33
34
36
36
36
37
38
38
38
41
41
41
41
42
43
43
43
43
44
44
45
45
45
45
45
4...

result:

ok 426 lines

Test #20:

score: 30
Accepted
time: 0ms
memory: 4076kb

input:

271
194 12
60 142
221 59
149 143
196 56
33 211
109 166
78 264
111 27
121 246
78 256
234 243
156 152
144 129
166 102
175 244
36 168
220 138
244 117
266 15
263 258
213 59
60 180
177 155
44 71
47 64
118 22
54 116
43 72
167 227
169 138
225 214
182 63
100 7
149 28
219 175
25 57
117 192
226 12
10 6
86 131...

output:

0
1
1
1
1
1
2
2
2
2
3
3
3
4
5
6
6
6
6
7

result:

ok 20 lines

Test #21:

score: 30
Accepted
time: 1ms
memory: 3792kb

input:

273
191 151
104 115
271 19
262 261
75 226
154 100
38 50
20 70
82 255
117 152
249 223
119 87
103 186
126 145
52 142
231 190
157 87
194 1
192 60
201 12
106 266
103 116
171 176
167 187
243 143
72 63
148 262
250 112
73 224
252 90
217 42
257 123
168 145
93 110
17 187
67 90
171 255
271 64
74 12
224 75
62 ...

output:

0
1
1
1
2
3
3
3
3
4
4
4
4
5
6
7
7
7
7
7
7
8
9
9
9
8
9
9
9
9
9
10
10
10
10
10
11
11
11
11
13
13
14
14
15
15
15
15
15
16
17
17
18
19
19
19
17
18
18
18
18
18
20
20
20
20
20
20
20
20
21
20
19
19
19
20
18
18
18
20
22
22
24
24
25
26
26
26
26
28
28
28
29
29
31
31
31
31
31
31
31
33
34
35
35
35
35
35
35
35
3...

result:

ok 387 lines

Test #22:

score: 30
Accepted
time: 1ms
memory: 3904kb

input:

337
281 1
334 256
301 20
260 129
24 120
45 73
123 95
138 276
275 271
71 202
182 85
320 159
72 223
332 299
287 165
63 328
282 197
104 252
253 182
29 212
65 201
133 65
115 306
46 10
237 269
182 69
32 252
240 304
257 71
326 214
84 282
322 253
164 298
22 127
66 303
165 307
143 188
137 319
280 82
274 282...

output:

0
1
1
1
1
2
3
3
3
3
3
4
4
4
4
5
5
5
5
5
5
6
6
7
7
7
8
9
9
9
9
9
9
9
9
9
9
11
11
11
14
15
15
17
17
17
17
16
16
16
16
16
16
16
16
17
17
17
17
18
18
18
18
18
18
18
19
19
19
19
19
20
20
20
21
21
21
21
22
24
25
25
26
25
25
25
24
27
27
28
28
30
30
31
32
33
33
31
31
32
32
32
32
32
32
33
33
34
34
34
34
34
3...

result:

ok 406 lines

Test #23:

score: 30
Accepted
time: 7ms
memory: 3828kb

input:

836
13 417
571 248
553 631
647 660
177 257
405 507
451 127
210 228
578 580
711 475
100 289
352 347
112 384
90 276
169 198
49 530
244 102
454 593
106 7
358 663
656 542
294 517
702 422
49 710
421 218
776 370
428 498
37 636
487 574
272 597
699 749
313 515
791 484
185 75
346 445
473 19
659 512
453 673
1...

output:

0
1
1
2
2
2
2
3
4
4
4
4
6
7
7
8
8
8
9
9
9
10
10
12
13
13
13
13
13
14
15
15
15
15
15
15
15
16
16
17
17
17
17
17
18
18
18
18
19
20
20
21
21
21
21
21
21
21
21
21
21
21
21
22
22
22
22
21
21
21
21
21
21
21
21
20
20
21
21
22
22
22
24
24
25
25
25
25
26
26
26
26
27
27
28
28
28
28
29
29
29
30
30
30
30
30
30
...

result:

ok 962 lines

Test #24:

score: 30
Accepted
time: 5ms
memory: 4080kb

input:

778
522 567
760 407
315 542
368 92
255 760
232 666
468 222
139 155
554 201
561 180
402 136
718 419
605 678
54 674
722 746
478 441
702 620
567 147
647 104
264 74
477 541
212 629
241 93
703 47
564 587
610 167
556 75
110 589
701 128
513 32
135 221
124 424
120 300
670 122
624 418
360 434
87 123
46 628
6...

output:

0
0
1
1
2
2
2
2
3
3
3
3
3
5
5
5
5
5
6
6
7
7
7
7
7
7
8
9
9
9
9
9
9
9
9
9
11
12
11
14
15
15
15
15
15
16
18
18
18
20
20
20
20
20
20
21
21
23
22
22
22
21
21
21
22
22
22
22
23
23
23
23
24
24
25
25
26
27
27
27
27
28
28
29
29
29
29
30
30
30
30
31
32
32
33
34
35
35
35
35
36
37
37
36
36
36
36
37
38
40
40
39
...

result:

ok 838 lines

Test #25:

score: 30
Accepted
time: 3ms
memory: 3908kb

input:

409
172 390
258 268
312 267
379 199
379 282
322 36
89 52
364 32
294 321
25 348
305 54
188 343
131 293
323 220
383 201
202 333
5 231
168 141
145 215
308 115
407 175
201 298
352 91
162 127
255 331
3 127
16 118
403 96
294 301
132 50
122 119
247 301
118 174
309 58
73 1
208 116
171 156
137 5
340 86
77 19...

output:

0
1
1
2
2
2
2
2
3
3
3
4
5
5
6
6
6
6
6
6
6
6
5
5
4
4
4
4
4
4
4
5
5
5
5
5
5
5
6
6
6
6
6
7
7
7
8
9
9
10
11
11
12
13
13
13
13
13
14
14
14
14
15
16
18
19
19
18
19
20
21
21
21
21
21
22
23
23
24
24
24
24
26
26
26
27
27
28
29
30
30
31
31
31
31
30
31
31
32
34
34
34
36
37
39
39
39
39
39
39
40
41
41
41
43
43
4...

result:

ok 753 lines

Test #26:

score: 30
Accepted
time: 1ms
memory: 3832kb

input:

435
392 219
251 271
361 365
282 190
343 388
272 224
355 240
333 29
115 127
148 42
70 195
266 9
20 120
226 321
277 184
107 12
46 228
378 342
97 94
244 58
220 416
45 365
435 63
140 357
399 273
203 264
317 266
318 307
400 312
141 106
295 326
8 43
33 101
125 118
329 290
353 12
163 341
347 160
33 269
238...

output:

0
1
1
1
1
1
1
1
1
1
2
3
4
4
4
4
5
7
8
9
10
10
10
10
10
10
10
11
11
11
11
11
11
12
12
14
14
15
15
15
15
15
16
16
17
17
18
18
18
18
19
18
20
22
22
22
22
22
22
22
22
23
24
24
24
24
24
24
24
24
24
24
25
25
23
23
23
23
22
23
24
24
25
25
25
25
27
28
27
28
29
29
28
28
29
29
30
31
31
31
32
32
35
32
32
31
31...

result:

ok 294 lines

Test #27:

score: 30
Accepted
time: 2ms
memory: 3832kb

input:

276
105 115
115 80
80 262
259 262
83 259
131 83
149 131
167 149
34 167
34 3
3 44
44 229
261 229
200 261
200 202
11 202
11 257
257 74
17 74
128 17
128 155
155 42
42 185
185 54
271 54
271 92
99 92
99 181
193 181
29 193
211 29
249 211
196 249
168 196
168 18
179 18
179 120
120 97
192 97
81 192
26 81
62 ...

output:

0
1
1
1
3
3
3
3
1
1
1
1
2
2
2
2
2
3
3
3
3
3
5
5
5
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
9
9
9
9
11
11
13
13
13
15
15
15
17
19
21
23
23
23
23
23
23
23
25
27
27
29
29
31
31
31
31
31
31
31
31
31
31
31
33
33
35
35
35
35
35
35
35
35
35
35
35
35
37
37
37
37
37
37
37
37
39
39
41
41
41
43
43
41
41
43
43
43
45
45
...

result:

ok 300 lines

Test #28:

score: 30
Accepted
time: 0ms
memory: 3868kb

input:

828
810 398
398 519
519 159
159 745
737 745
737 552
552 38
277 38
277 258
258 196
196 807
365 807
365 765
765 339
301 339
301 463
463 427
276 427
734 276
734 244
98 244
498 98
403 498
403 139
139 415
334 415
687 334
687 41
172 41
172 470
814 470
701 814
701 740
740 43
630 43
270 630
270 471
471 9
9 ...

output:

0
0
0
0
2
3
4
4
4
4
4
4
6
6
6
6
6
6
8
8
8
10
12
12
12
14
16
16
16
18
18
18
18
18
18
18
16
16
18
18
20
20
22
22
22
22
22
24
24
24
24
24
24
24
26
26
28
28
28
28
28
28
28
28
28
28
28
28
30
30
30
32
32
32
32
32
32
32
32
34
34
34
34
34
36
35
35
35
37
39
39
39
39
39
39
39
39
39
39
39
41
39
39
39
41
43
43
...

result:

ok 184 lines

Test #29:

score: 30
Accepted
time: 14ms
memory: 4180kb

input:

820
651 295
78 651
8 78
470 8
451 470
727 451
727 445
445 117
202 117
202 802
802 71
17 71
17 812
812 472
472 3
171 3
171 166
166 715
173 715
173 168
168 410
410 744
744 416
416 85
85 27
485 27
485 149
149 496
528 496
818 528
103 818
97 103
97 217
217 139
653 139
471 653
471 264
264 561
297 561
603 ...

output:

0
0
0
1
1
1
1
1
3
3
3
5
5
5
5
5
7
7
7
7
7
7
7
9
7
7
7
9
9
9
11
11
13
15
15
15
15
15
17
17
17
19
21
21
23
23
23
23
23
23
23
23
23
23
25
27
27
27
27
29
29
31
31
31
31
31
31
33
35
35
37
37
37
37
37
37
37
37
37
39
39
41
41
41
41
39
39
41
41
41
41
41
41
43
43
43
43
43
43
43
43
45
45
45
45
45
45
45
47
47
...

result:

ok 1000 lines

Test #30:

score: 30
Accepted
time: 1ms
memory: 3796kb

input:

220
164 138
81 138
174 138
213 138
60 138
16 138
138 32
26 138
138 44
138 29
45 138
138 182
13 138
138 151
138 6
138 93
206 138
80 138
138 90
138 207
138 150
138 100
8 138
138 106
138 27
138 212
217 138
161 138
138 122
138 133
94 138
120 138
138 42
121 138
5 138
136 138
138 135
138 66
138 51
55 138
...

output:

0
0
1
1
2
2
3
3
3
3
4
5
5
6
6
6
7
7
8
8
8
9
10
10
11
12
13
14
14
15
15
16
16
16
16
16
17
18
18
19
19
20
21
21
21
21
22
23
23
24
24
25
25
25
25
25
25
24
24
24
25
25
25
25
25
26
27
28
29
30
30
29
30
29
29
30
31
32
31
31
31
31
32
32
31
32
33
33
34
34
34
34
34
34
33
34
35
36
36
37
37
37
38
37
37
36
35
3...

result:

ok 561 lines

Test #31:

score: 30
Accepted
time: 1ms
memory: 3808kb

input:

800
72 287
596 287
693 287
655 287
168 287
325 287
287 795
774 287
287 118
429 287
287 575
287 247
287 155
119 287
287 447
287 374
287 378
344 287
587 287
287 607
287 389
324 287
287 137
51 287
287 215
287 142
260 287
149 287
287 245
192 287
287 577
287 559
573 287
159 287
287 502
754 287
346 287
28...

output:

0
0
1
1
1
1
1
1
1
1
1
2
3
4
5
6
6
7
8
8
9
9
10
10
11
12
13
14
14
14
15
16
16
16
17
18
18
18
18
19
19
19
19
19
20
21
22
22
22
23
24
25
25
25
25
26
27
28
29
29
30
31
31
32
32
33
33
34
34
34
34
34
35
35
34
35
36
36
36
36
37
38
38
38
38
38
38
37
38
39
39
39
39
39

result:

ok 94 lines

Test #32:

score: 30
Accepted
time: 2ms
memory: 4060kb

input:

292
107 53
176 53
53 1
267 53
157 53
53 213
53 19
53 43
53 172
53 169
2 53
63 53
53 150
188 53
53 255
53 50
225 53
53 158
53 216
38 53
272 53
121 53
53 92
49 53
3 53
53 209
53 75
143 53
95 53
275 53
53 178
53 282
53 236
31 53
53 263
119 53
290 53
226 53
53 214
53 10
53 229
262 53
149 53
193 53
23 53...

output:

0
1
1
2
2
3
3
3
4
4
4
4
5
5
6
7
7
7
8
8
9
9
9
10
11
12
13
13
14
15
15
16
15
16
16
17
17
17
17
18
18
18
17
18
18
18
18
18
19
19
18
18
18
19
19
19
19
20
21
21
22
23
23
23
24
25
25
25
25
25
25
25
25
24
23
23
24
25
26
27
28
28
29
30
31
31
32
32
32
32
32
31
30
29
29
29
30
31
31
32
33
32
32
32
31
31
31
32...

result:

ok 703 lines

Subtask #3:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #33:

score: 0
Time Limit Exceeded

input:

50516
80 25781
27578 39138
42128 34705
31858 9513
10874 47059
13846 22138
6315 27891
44827 23006
44544 26597
9205 1572
3857 18166
28675 43775
6486 15805
23949 32263
42848 17311
21484 155
27144 42220
30798 6582
3641 36355
1695 8694
15029 38762
38309 25196
45604 11904
13989 4290
39713 48125
36823 9220...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-11-29 19:49:17 | OpenSource Project