QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#123380#3711. Floyd-Warshallzjy0001AC ✓657ms73644kbC++171.5kb2023-07-12 14:27:362023-07-12 14:27:37

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-12 14:27:37]
  • Judged
  • Verdict: AC
  • Time: 657ms
  • Memory: 73644kb
Show
  • [2023-07-12 14:27:36]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
inline int read(){
	int x=0,f=1;char ch;
	while(!isdigit(ch=getchar()))if(ch=='-')f=-f;
	do x=(x<<3)+(x<<1)+(ch^48);while(isdigit(ch=getchar()));
	return x*f;
}
const int N=1e5+5;
int n,m,q,cnt;
int dis[205][N];
int f[N][18];
vector<int>G[N];
void bfs(int st){
    ++cnt;
    queue<int>Q;
    Q.push(st);
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        for(int v:G[x])
            if(v!=st&&!dis[cnt][v])
                dis[cnt][v]=dis[cnt][x]+1,Q.push(v);
    }
}
void dfs(int x,int fa){
    dis[0][x]=dis[0][fa]+1,f[x][0]=fa;
    for(int i=0;f[x][i];++i)
        f[x][i+1]=f[f[x][i]][i];
    for(int v:G[x]){
        if(v==fa)continue;
        if(dis[0][v])bfs(x);
        else dfs(v,x);
    }
}
int LCA(int x,int y){
    if(dis[0][x]<dis[0][y])swap(x,y);
    for(int h=dis[0][x]-dis[0][y],i=0;h;h>>=1,++i)
        if(h&1)x=f[x][i];
    if(x==y)return x;
    for(int i=17;~i;--i)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
int query(int u,int v){
    int res=dis[0][u]+dis[0][v]-2*dis[0][LCA(u,v)];
    for(int i=1;i<=cnt;++i)res=min(res,dis[i][u]+dis[i][v]);
    return res;
}
signed main(){
	n=read(),m=read(),q=read();
	for(int i=1;i<=m;++i){
        int u=read(),v=read();
        G[u].push_back(v),G[v].push_back(u);
	}
	dfs(1,0);
    for(int i=1;i<=q;++i){
        int u=read(),v=read();
        printf("%d\n",query(u,v));
    }
	return 0;
}
源文件, 语言: C++17

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7220kb

input:

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

output:

0
1
2

result:

ok 3 number(s): "0 1 2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 7180kb

input:

1 2 1
1 1
1 1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 2ms
memory: 7892kb

input:

5 7 10
5 3
1 2
4 1
2 5
3 4
2 2
1 3
5 5
4 5
3 2
4 4
5 3
3 5
2 4
4 2
5 3
4 2

output:

0
2
2
0
1
1
2
2
1
2

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 6340kb

input:

5 8 10
5 1
1 3
4 5
2 3
1 5
4 2
2 2
2 3
2 1
2 3
4 5
1 1
2 2
5 3
3 5
3 4
4 5
1 1

output:

2
1
1
0
0
2
2
2
1
0

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 2ms
memory: 7368kb

input:

5 8 10
4 1
5 2
3 5
3 1
5 1
5 1
4 2
2 5
3 1
3 2
2 1
3 2
3 3
1 5
4 5
4 3
4 3
2 5

output:

1
2
2
2
0
1
2
2
2
1

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 2ms
memory: 7100kb

input:

5 6 10
3 5
5 1
1 4
5 2
5 4
4 1
3 3
4 5
1 5
1 4
2 5
1 4
3 3
2 1
5 1
1 4

output:

0
1
1
1
1
1
0
2
1
1

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 2ms
memory: 7048kb

input:

5 8 10
2 3
5 3
1 4
3 1
5 5
1 2
2 5
1 2
3 5
2 5
3 5
3 2
3 2
2 5
2 4
1 2
2 2
5 2

output:

1
1
1
1
1
1
2
1
0
1

result:

ok 10 numbers

Test #8:

score: 0
Accepted
time: 1ms
memory: 6492kb

input:

5 7 10
1 3
4 1
4 2
5 4
4 1
5 4
3 5
2 3
1 1
5 4
4 3
1 1
3 3
3 1
2 3
5 5
2 5

output:

3
0
1
2
0
0
1
3
0
2

result:

ok 10 numbers

Test #9:

score: 0
Accepted
time: 0ms
memory: 6352kb

input:

5 8 10
1 2
1 5
4 1
2 3
4 5
3 3
4 1
2 5
5 1
5 3
3 4
1 5
1 4
3 5
1 4
1 3
5 4
2 4

output:

1
2
3
1
1
2
1
2
1
2

result:

ok 10 numbers

Test #10:

score: 0
Accepted
time: 1ms
memory: 6008kb

input:

5 7 10
5 2
2 1
5 3
3 4
1 5
1 1
5 3
4 5
3 1
3 1
3 1
2 1
2 1
5 1
4 4
5 3
3 2

output:

2
2
2
2
1
1
1
0
1
2

result:

ok 10 numbers

Test #11:

score: 0
Accepted
time: 2ms
memory: 7240kb

input:

5 8 10
1 5
3 5
2 5
1 4
4 1
3 3
5 5
5 2
1 5
2 3
2 2
3 4
3 2
1 1
5 3
3 4
5 4
2 4

output:

1
2
0
3
2
0
1
3
2
3

result:

ok 10 numbers

Test #12:

score: 0
Accepted
time: 2ms
memory: 6816kb

input:

5 7 10
5 1
5 3
2 5
4 2
3 3
3 2
2 2
1 5
2 3
2 2
5 4
3 3
2 5
5 5
3 4
2 2
5 5

output:

1
1
0
2
0
1
0
2
0
0

result:

ok 10 numbers

Test #13:

score: 0
Accepted
time: 2ms
memory: 7888kb

input:

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

output:

2
2
4
2
1
1
3
1
1
2

result:

ok 10 numbers

Test #14:

score: 0
Accepted
time: 1ms
memory: 6040kb

input:

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

output:

4
3
0
4
1
1
0
3
1
0

result:

ok 10 numbers

Test #15:

score: 0
Accepted
time: 2ms
memory: 6736kb

input:

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

output:

2
2
2
1
2
3
3
1
0
2

result:

ok 10 numbers

Test #16:

score: 0
Accepted
time: 1ms
memory: 7552kb

input:

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

output:

0
1
3
1
3
2
3
0
0
4

result:

ok 10 numbers

Test #17:

score: 0
Accepted
time: 0ms
memory: 6092kb

input:

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

output:

2
3
1
0
2
1
0
3
3
1

result:

ok 10 numbers

Test #18:

score: 0
Accepted
time: 2ms
memory: 7228kb

input:

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

output:

5
0
0
5
1
3
1
2
1
1

result:

ok 10 numbers

Test #19:

score: 0
Accepted
time: 1ms
memory: 7940kb

input:

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

output:

1
2
1
4
2
3
1
1
2
3

result:

ok 10 numbers

Test #20:

score: 0
Accepted
time: 2ms
memory: 7512kb

input:

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

output:

1
2
1
0
2
1
2
3
1
1

result:

ok 10 numbers

Test #21:

score: 0
Accepted
time: 0ms
memory: 6716kb

input:

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

output:

4
3
2
2
1
0
2
0
3
2

result:

ok 10 numbers

Test #22:

score: 0
Accepted
time: 2ms
memory: 6928kb

input:

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

output:

1
2
0
2
2
3
1
2
1
2

result:

ok 10 numbers

Test #23:

score: 0
Accepted
time: 2ms
memory: 6712kb

input:

100 154 1000
35 12
42 72
44 83
47 99
100 98
27 73
83 25
78 91
44 2
67 22
58 12
78 76
58 67
77 45
62 77
75 31
53 62
48 19
69 13
12 90
48 5
60 37
99 45
63 29
46 32
65 23
94 86
80 17
89 73
55 91
46 57
81 20
26 85
28 38
33 63
67 89
46 12
18 77
86 73
42 39
66 55
47 33
24 20
4 83
83 96
54 46
88 1
37 36
42...

output:

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

result:

ok 1000 numbers

Test #24:

score: 0
Accepted
time: 3ms
memory: 8576kb

input:

100 189 1000
79 57
24 34
21 66
39 58
82 38
67 63
12 48
99 13
3 20
11 71
40 25
62 33
66 88
38 54
33 99
53 18
90 71
44 53
40 46
23 87
62 98
6 26
83 52
3 47
17 50
21 12
18 82
14 8
2 24
59 3
63 92
63 51
84 70
51 29
59 8
57 100
58 95
56 37
73 30
54 94
22 81
62 76
92 80
46 32
6 34
67 49
53 19
24 44
89 42
...

output:

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

result:

ok 1000 numbers

Test #25:

score: 0
Accepted
time: 2ms
memory: 7736kb

input:

100 125 1000
24 11
1 87
86 42
27 14
64 74
23 61
53 63
16 36
57 38
60 11
25 31
41 90
74 5
99 66
3 25
24 9
18 84
52 83
7 88
33 79
81 79
68 14
63 68
47 65
72 64
73 2
43 86
49 91
27 79
67 10
68 39
41 82
49 54
71 28
97 57
39 19
62 70
87 97
56 87
62 44
71 12
86 7
68 52
93 82
28 72
83 56
10 28
22 61
40 80
...

output:

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

result:

ok 1000 numbers

Test #26:

score: 0
Accepted
time: 2ms
memory: 6548kb

input:

100 156 1000
72 69
79 45
63 29
15 69
46 17
62 55
83 86
25 58
11 60
5 64
3 48
24 51
91 26
52 86
69 43
2 5
55 84
52 12
82 26
40 76
95 64
23 11
42 76
91 87
42 73
17 91
67 82
87 74
48 26
79 21
90 75
19 17
10 43
99 19
31 14
38 35
78 46
21 54
39 32
70 91
27 42
14 41
28 24
44 31
51 6
96 68
75 37
12 69
88 2...

output:

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

result:

ok 1000 numbers

Test #27:

score: 0
Accepted
time: 0ms
memory: 7868kb

input:

100 191 1000
20 14
57 98
36 100
3 29
29 57
6 46
24 1
42 80
65 78
50 12
81 57
95 12
7 47
13 99
40 74
72 96
87 93
60 42
57 63
59 73
14 45
77 100
26 87
27 5
97 91
69 84
95 74
22 64
69 81
83 25
95 10
96 40
64 20
65 58
20 58
89 17
51 6
26 85
86 42
83 69
38 84
100 88
86 81
70 44
16 79
40 46
10 77
47 56
19...

output:

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

result:

ok 1000 numbers

Test #28:

score: 0
Accepted
time: 2ms
memory: 6440kb

input:

100 127 1000
61 68
30 52
4 83
91 88
11 100
46 36
57 24
59 95
24 4
2 61
67 66
78 69
15 68
74 19
6 100
47 87
31 6
61 76
32 1
65 74
28 34
36 4
13 7
71 19
68 13
24 69
16 66
60 55
94 36
92 36
8 49
78 71
29 5
42 21
99 7
6 73
97 92
81 58
9 38
89 96
39 95
66 15
72 59
33 35
89 78
29 82
5 55
97 93
94 2
31 40
...

output:

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

result:

ok 1000 numbers

Test #29:

score: 0
Accepted
time: 3ms
memory: 6684kb

input:

100 162 1000
5 13
8 13
81 63
79 44
97 48
97 30
94 47
76 21
86 22
43 1
44 76
58 26
24 90
76 14
21 82
64 7
69 2
3 38
84 67
39 19
90 93
97 18
15 37
22 27
64 55
36 66
98 42
15 83
4 43
29 84
60 7
94 90
70 12
37 60
93 92
5 68
11 18
96 83
5 39
91 25
86 50
36 31
11 16
37 89
70 68
95 2
41 44
55 17
71 36
62 9...

output:

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

result:

ok 1000 numbers

Test #30:

score: 0
Accepted
time: 3ms
memory: 7024kb

input:

100 193 1000
49 75
85 67
54 42
68 3
76 88
41 16
28 58
97 36
36 40
92 54
22 93
41 87
44 7
92 52
50 40
100 73
100 19
69 35
78 76
91 71
61 96
45 82
85 30
51 55
89 40
20 52
64 58
36 38
8 47
34 23
42 38
60 71
90 11
63 9
79 7
16 39
46 78
79 40
13 89
44 60
9 93
4 95
26 54
54 1
31 78
93 18
93 78
80 90
41 45...

output:

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

result:

ok 1000 numbers

Test #31:

score: 0
Accepted
time: 2ms
memory: 7464kb

input:

100 130 1000
90 21
67 17
23 29
60 59
58 31
85 7
65 85
6 62
98 63
37 2
8 98
24 44
52 28
49 64
21 58
66 60
32 28
73 65
53 17
97 60
76 89
95 78
60 41
95 77
48 58
72 33
85 54
71 20
57 86
16 58
51 58
24 61
17 56
13 2
97 54
61 18
28 14
72 34
66 93
21 44
100 86
29 24
80 67
76 80
53 87
66 4
100 87
79 26
44 ...

output:

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

result:

ok 1000 numbers

Test #32:

score: 0
Accepted
time: 3ms
memory: 7024kb

input:

100 151 1000
13 29
25 59
82 88
71 73
29 91
48 39
73 20
26 45
45 9
98 8
38 3
13 96
12 2
74 18
89 59
50 22
38 90
63 55
41 36
70 98
87 94
86 27
40 21
66 92
90 32
10 3
62 73
19 40
71 87
94 33
57 61
25 49
43 78
30 26
89 80
35 49
72 58
76 49
44 98
84 2
92 82
91 97
10 25
36 16
47 72
78 47
42 6
87 72
47 82
...

output:

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

result:

ok 1000 numbers

Test #33:

score: 0
Accepted
time: 7ms
memory: 6584kb

input:

1000 1015 50000
6 721
586 869
596 598
400 723
147 491
711 8
990 473
318 688
493 260
742 800
274 252
405 133
526 270
577 343
694 596
100 750
762 946
963 499
888 828
491 417
850 911
161 745
20 293
507 118
415 700
981 66
985 583
726 63
739 907
24 831
626 747
499 357
534 901
2 682
581 931
4 985
489 667
...

output:

15
25
32
30
27
5
13
14
24
26
27
15
31
18
22
19
0
16
16
22
23
23
14
6
20
30
17
15
31
11
31
15
18
7
17
17
21
20
31
18
22
17
28
27
24
27
11
12
20
15
6
27
19
26
25
6
24
15
12
30
10
13
22
19
21
20
23
16
26
32
23
18
13
14
31
10
24
19
26
21
22
14
29
11
23
21
37
15
11
35
7
16
10
19
25
10
20
23
13
15
15
17
1...

result:

ok 50000 numbers

Test #34:

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

input:

1000 1050 50000
146 979
64 419
372 477
92 582
625 931
455 99
527 692
939 602
947 278
982 741
52 465
330 212
317 354
387 390
255 569
772 183
828 563
362 676
333 440
103 121
902 198
9 99
245 260
560 15
974 232
467 689
609 258
220 174
347 919
543 610
641 870
903 778
864 142
658 692
136 334
368 650
220 ...

output:

8
16
10
13
16
16
19
10
18
11
21
6
15
13
17
14
15
17
6
16
13
14
11
16
12
15
21
15
19
8
12
17
19
13
12
19
15
13
13
24
22
19
4
20
16
8
15
14
18
14
11
10
19
13
20
14
18
11
12
16
8
4
19
12
9
12
8
12
14
12
15
14
10
16
7
18
8
8
9
4
12
18
10
10
13
16
12
16
12
0
27
11
22
9
10
18
17
12
22
17
17
16
19
16
11
24...

result:

ok 50000 numbers

Test #35:

score: 0
Accepted
time: 11ms
memory: 7708kb

input:

1000 1085 50000
502 724
246 481
341 756
80 546
807 370
495 893
961 311
857 29
505 1000
927 489
341 975
713 69
525 871
248 702
421 987
43 770
965 864
474 406
408 678
214 221
824 979
463 800
224 368
804 633
633 346
519 270
430 154
158 60
671 670
51 122
450 206
693 810
525 927
781 291
270 883
450 665
7...

output:

15
21
11
10
4
10
6
13
5
15
7
10
10
14
13
15
17
13
16
13
13
9
8
15
15
15
14
13
9
1
22
11
15
8
10
7
13
14
13
13
19
20
11
8
10
17
14
11
13
10
11
18
15
12
17
14
15
13
19
5
9
11
12
14
13
6
13
16
13
8
10
10
13
13
11
15
16
14
5
12
16
12
16
13
1
15
16
10
8
13
1
12
12
24
8
10
11
8
10
11
13
10
15
15
9
16
14
1...

result:

ok 50000 numbers

Test #36:

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

input:

1000 1017 50000
347 982
723 734
414 444
68 701
693 514
238 983
498 634
774 943
959 18
680 238
119 484
96 926
542 796
301 119
291 509
121 869
397 972
371 135
483 915
324 514
939 272
109 989
308 691
344 547
99 460
763 68
58 346
393 651
292 821
664 825
363 541
267 545
83 608
905 82
596 728
940 488
435 ...

output:

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

result:

ok 50000 numbers

Test #37:

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

input:

1000 1052 50000
487 536
97 796
191 619
248 561
172 954
86 73
635 149
691 666
222 37
921 986
193 801
967 487
454 17
162 431
162 735
391 456
533 785
483 865
558 153
835 615
157 53
972 689
391 799
884 165
758 277
519 353
582 946
627 242
913 868
468 336
876 684
249 768
448 689
325 681
434 85
23 800
651 ...

output:

8
13
15
10
18
18
11
12
20
10
18
21
17
23
24
11
8
14
17
19
8
17
11
9
13
7
16
8
12
18
16
20
15
15
17
21
10
17
19
12
7
12
20
11
16
12
12
9
13
9
19
22
7
13
19
20
12
10
18
19
14
10
18
14
17
15
15
16
21
11
6
15
11
19
13
11
11
16
17
13
11
13
12
19
16
18
15
11
12
10
13
17
10
15
16
19
15
16
12
18
10
13
16
12...

result:

ok 50000 numbers

Test #38:

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

input:

1000 1087 50000
331 281
575 49
160 602
940 420
354 393
534 868
172 472
800 284
972 463
866 631
779 607
351 48
366 535
23 255
32 153
766 451
966 598
187 299
825 390
946 612
272 834
426 878
475 610
128 79
225 495
866 638
699 138
565 321
534 723
976 744
789 723
527 799
813 178
152 280
568 930
913 519
1...

output:

10
10
15
14
8
16
13
4
11
12
13
12
11
19
9
8
13
11
16
11
14
12
12
8
10
13
9
5
12
12
12
17
7
16
11
9
12
16
12
13
13
13
6
10
14
18
18
11
14
13
18
14
22
10
12
5
8
11
8
8
11
9
14
10
14
12
14
5
10
11
14
11
12
7
19
4
11
11
10
14
19
15
12
10
17
16
14
17
13
10
8
6
9
14
10
11
11
7
7
14
10
11
12
14
16
11
13
13...

result:

ok 50000 numbers

Test #39:

score: 0
Accepted
time: 9ms
memory: 7716kb

input:

1000 1023 50000
472 835
756 303
936 778
224 576
240 833
573 958
605 987
717 711
234 481
914 379
556 116
30 905
382 756
780 864
198 380
740 38
102 899
787 325
196 628
161 905
682 319
585 67
263 422
372 505
884 609
814 731
31 138
608 208
859 578
588 255
111 58
804 534
475 859
276 71
702 479
403 534
67...

output:

21
17
9
18
12
22
5
18
12
41
18
22
13
8
25
24
22
10
6
7
13
24
29
11
13
21
15
21
16
13
5
26
17
16
10
34
22
12
24
13
12
27
23
21
28
10
15
17
12
18
20
11
8
23
9
12
9
28
11
15
26
29
21
21
15
13
17
20
25
8
25
24
21
19
27
10
24
32
28
10
10
24
23
22
13
13
11
11
29
15
8
17
14
22
14
17
25
18
13
16
14
26
4
24
...

result:

ok 50000 numbers

Test #40:

score: 0
Accepted
time: 18ms
memory: 7648kb

input:

1000 1054 50000
20 285
234 364
713 465
212 731
423 80
317 152
143 311
338 625
88 203
859 128
38 625
413 762
591 977
937 176
365 310
11 433
534 7
195 758
271 570
271 301
605 908
39 64
538 233
208 123
350 426
866 16
851 34
842 798
672 625
393 958
216 97
786 565
32 644
696 670
836 131
486 549
82 608
90...

output:

12
14
11
14
13
15
11
23
10
11
15
5
17
13
11
13
13
14
13
10
10
18
7
13
10
18
9
20
15
20
17
10
12
10
16
11
21
17
20
10
16
13
12
13
25
14
21
16
17
22
14
15
16
17
18
20
10
14
16
19
15
17
19
13
15
14
14
16
9
7
8
9
17
10
15
19
14
23
14
14
8
12
20
15
7
14
18
8
10
13
17
14
16
11
12
15
18
8
5
16
15
7
19
14
1...

result:

ok 50000 numbers

Test #41:

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

input:

1000 1089 50000
673 838
903 618
978 936
904 591
901 224
357 946
576 826
255 348
543 221
100 68
816 942
284 323
799 494
694 297
235 24
385 724
671 116
795 192
346 911
678 298
15 393
494 252
622 45
452 37
305 836
918 110
480 930
780 685
589 480
901 470
833 432
168 789
397 429
523 461
866 680
272 76
59...

output:

16
8
16
13
12
10
13
16
9
15
14
11
14
18
10
19
15
14
13
13
12
18
9
11
12
13
10
17
11
7
13
13
12
14
11
12
13
14
10
14
14
5
11
9
12
10
11
7
8
15
17
12
14
10
8
11
16
13
10
16
7
9
17
9
14
12
14
8
13
17
12
11
5
11
2
13
12
12
13
9
14
10
8
12
11
5
6
20
15
8
11
6
13
14
13
17
18
21
11
11
5
12
13
14
14
10
16
8...

result:

ok 50000 numbers

Test #42:

score: 0
Accepted
time: 7ms
memory: 8120kb

input:

1000 1027 50000
992 158
594 578
127 938
253 413
890 427
140 81
764 958
389 390
23 93
465 70
848 925
849 323
654 281
863 878
470 797
216 161
66 995
601 255
213 698
215 662
480 522
205 556
793 465
162 983
791 521
392 804
815 135
647 121
26 406
271 442
748 466
329 975
303 942
191 837
262 694
944 249
58...

output:

16
7
13
24
4
24
17
20
19
15
18
26
17
21
9
17
10
14
23
20
14
16
21
16
17
23
12
13
9
16
21
19
16
9
25
15
26
19
17
24
18
21
26
25
19
18
18
16
22
5
18
12
18
28
21
8
18
17
4
25
15
15
20
22
22
23
23
12
18
15
21
25
21
14
18
23
17
22
18
20
19
13
31
20
17
4
9
13
15
19
17
19
7
13
10
14
27
22
14
14
22
12
23
13...

result:

ok 50000 numbers

Test #43:

score: 0
Accepted
time: 332ms
memory: 44772kb

input:

100000 100035 100000
55912 20481
12801 52825
48877 24980
54900 74881
91178 97116
28320 49056
75127 11930
7478 926
81725 73278
26073 27896
14872 49488
76480 89855
73788 75019
50647 31063
60845 71676
54238 86489
8741 60391
88936 48945
23250 17090
5022 93216
43637 62745
26490 38523
16228 52680
9548 269...

output:

36
69
103
132
65
67
85
61
86
102
70
107
110
94
87
70
46
81
55
50
121
105
100
63
96
65
111
124
108
62
82
74
99
116
137
102
57
128
99
61
135
19
71
156
93
83
98
95
86
111
75
39
109
90
31
62
83
102
42
50
61
85
57
103
104
151
99
76
96
136
89
97
20
102
108
89
62
81
104
64
101
76
113
93
90
126
133
90
49
11...

result:

ok 100000 numbers

Test #44:

score: 0
Accepted
time: 620ms
memory: 69024kb

input:

100000 100066 100000
4756 1034
42279 77886
51845 96963
6184 41741
62657 90260
88064 49146
77369 82253
55395 48649
29283 4000
90313 91645
62650 89701
18159 3712
83996 1944
99700 88479
28011 90902
31804 4588
60685 29796
83537 75163
86028 71624
38237 33509
61751 61230
60944 96712
77311 66788
33792 9341...

output:

106
94
95
93
78
80
42
130
84
82
119
155
79
64
115
77
85
65
51
124
98
106
106
120
79
17
119
97
105
103
67
74
56
48
132
112
128
98
63
52
100
50
99
71
78
76
114
87
123
90
58
76
128
130
69
76
78
114
59
104
97
98
127
110
90
113
93
76
99
64
58
100
91
53
75
42
95
75
107
101
80
53
93
88
78
78
62
72
105
81
8...

result:

ok 100000 numbers

Test #45:

score: 0
Accepted
time: 92ms
memory: 22084kb

input:

100000 100006 100000
86305 71188
4460 94436
30622 68946
22876 75896
66839 50700
23616 49237
3802 52576
60208 53267
9545 2018
63066 79586
10428 97211
92542 17569
2716 96165
57265 2792
70985 34320
17883 46879
4117 88801
53945 42596
16103 91566
95643 16906
47162 59715
28103 54900
71099 13599
25332 5132...

output:

92
105
217
205
221
197
83
115
61
192
183
105
104
159
93
78
124
54
106
126
180
162
184
176
128
117
170
192
214
109
190
93
140
122
102
102
142
137
140
65
84
205
170
85
206
141
148
39
118
130
61
129
152
177
197
99
67
132
71
59
72
229
188
76
230
123
196
192
35
110
93
122
66
74
225
63
93
94
237
190
110
1...

result:

ok 100000 numbers

Test #46:

score: 0
Accepted
time: 347ms
memory: 46276kb

input:

100000 100037 100000
2445 51742
33938 43690
76695 65122
6864 10052
3725 19651
50655 82031
6043 14387
8125 990
48591 32740
27307 76038
34014 80528
34221 64130
12925 57682
49422 17104
70856 20843
28153 56466
47550 23614
48545 77326
13474 78803
85754 89902
41084 68600
62557 88897
32182 60411
16872 4194...

output:

100
109
188
137
127
147
75
68
6
74
91
31
108
98
96
74
40
71
82
66
139
86
71
99
40
127
91
68
90
117
103
70
83
98
106
116
113
70
73
86
28
73
96
53
58
144
97
90
63
139
119
143
72
95
41
109
189
88
101
176
100
126
81
129
141
118
114
79
94
67
56
122
123
110
92
124
153
47
95
103
89
130
96
90
89
103
193
90
...

result:

ok 100000 numbers

Test #47:

score: 0
Accepted
time: 657ms
memory: 73644kb

input:

100000 100072 100000
27097 56487
87608 68751
12368 69809
90852 52719
7907 80091
10399 82121
99772 17414
56042 5608
28854 30758
24252 39787
49087 88037
32797 10691
55837 51903
31179 7224
70726 40069
14232 98757
90982 25722
18953 12056
43549 66041
18969 30195
59199 67085
97012 12494
25970 7222
41116 3...

output:

52
95
83
101
64
96
46
76
89
137
65
53
62
79
98
57
119
77
95
124
119
69
55
74
88
129
65
96
55
101
64
75
70
99
97
93
51
55
72
80
109
100
107
72
97
64
119
72
68
45
84
42
100
76
95
87
63
115
64
58
65
125
19
97
94
71
94
65
91
46
85
126
108
45
81
71
86
88
70
78
80
129
73
96
70
112
84
80
45
77
18
83
76
77
...

result:

ok 100000 numbers
English 繁體中文 简体中文

服务器时间: 2025-02-08 17:15:07 | 开源项目