QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#949390#10179. 입자 가속기KiharaTouma#16 136ms31336kbC++143.6kb2025-03-23 21:08:042025-03-23 21:08:04

Judging History

This is the latest submission verdict.

  • [2025-03-23 21:08:04]
  • Judged
  • Verdict: 16
  • Time: 136ms
  • Memory: 31336kb
Show
  • [2025-03-23 21:08:04]
  • Submitted

answer

//qoj10179
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, fa[N], ban[N], nw, siz[N], hav[N], stn;
vector<int> g[N];
vector<int> qq[N];
int nt, vis[N];

void initialize(int N, vector<int> A, vector<int> B){
    n = N;
    stn = 1;
    nt = 1;
    for(int i = 1; i <= n; ++ i){
        vector<int> ().swap(g[i]);
        vector<int> ().swap(qq[i]);
        fa[i] = 1;
        ban[i] = siz[i] = 0;
        hav[i] = 0;
        vis[i] = 0;
    }
    for(int i = 0; i < n - 1; ++ i){
        g[A[i]+1].push_back(B[i] + 1);
        g[B[i]+1].push_back(A[i] + 1);
    }
}

int dqh[N];
int generate(int u, bool res){
    ++ u;
    ++ nt;
    if(res == 1){
        nw -= siz[fa[u]] / 2;
        ++ siz[fa[u]];
        hav[u] = 1;
        nw += siz[fa[u]] / 2;
        return nw;
    }
    ban[u] = 1;
    nw -= siz[fa[u]] / 2;
    static int ss[N], ql[N], qr[N], sm[N];
    int tp = 0;
    for(int i : g[u]){
        if(!ban[i]){
            ss[++tp] = i;
            vector<int> ().swap(qq[tp]);
            qq[tp].push_back(i);
            dqh[i] = 0;
            ql[tp] = qr[tp] = 0;
            vis[i] = nt;
            sm[tp] = 0;
        }
    }
    int ed = 0;
    vis[u] = nt;
    while(ed < tp - 1){
        for(int i = 1; i <= tp; ++ i){
            if(ql[i] <= qr[i]){
                int x = qq[i][ql[i]];
                ++ ql[i];
                // for(int y : g[x]){
                for(int j = dqh[x]; j < g[x].size(); ++ j){
                    dqh[x] = j;
                    int y = g[x][j];
                    if(!ban[y] && vis[y] != nt){
                        vis[y] = nt;
                        ++ qr[i];
                        qq[i].push_back(y);
                        dqh[y] = 0;
                        break;
                    }
                }
                if(ql[i] > qr[i]){
                    sm[i] = 1;
                    ++ ed;
                }
            }
            if(ed == tp - 1){
                break;
            }
        }
    }
    int lp = fa[u];
    for(int i = 1; i <= tp; ++ i){
        if(sm[i]){
            // printf("[%d]: ", i);
            ++ stn;
            for(int j : qq[i]){
                // printf("%d ", j);
                fa[j] = stn;
                if(hav[j]){
                    ++ siz[stn];
                    -- siz[lp];
                }
            }
            nw += siz[stn] / 2;
            // puts("");
        }
    }
    nw += siz[lp] / 2;
    return nw;
}

#ifndef ONLINE_JUDGE

void my_assert(bool x){
    if (!x){
        puts("Wrong input");
        exit(0);
    }
}
 
int main(){
    int N, Q;
    my_assert(scanf("%d %d", &N, &Q) == 2);
    
    std::vector<int> A(N-1), B(N-1);
    static int tt[200010];
    for (int i=0;i<N-1;i++){
        // tt[i] = i;
        // A[i] = i+1;
        // B[i] = rand() % (i + 1);
        my_assert(scanf("%d %d", &A[i], &B[i]) == 2);
        my_assert(0 <= A[i] && A[i] <= N-1);
        my_assert(0 <= B[i] && B[i] <= N-1);
        my_assert(A[i] != B[i]);
    }
    tt[N-1] = N-1;
    random_shuffle(tt, tt + N);
    initialize(N, A, B);
    std::vector<int> ans(Q);
    std::vector<int> V(Q), R(Q);
    for (int i=0;i<Q;i++){
        // V[i] = tt[i];
        // R[i] = 0;
        my_assert(scanf("%d %d", &V[i], &R[i]) == 2);
        my_assert(0 <= V[i] && V[i] <= N-1);
        my_assert(R[i] == 0 || R[i] == 1);
        ans[i] = generate(V[i], R[i]==1);
        printf("%d %d\n", i, ans[i]);
    }
    cerr << stn << '\n';
}

#endif
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 9
Accepted
time: 1ms
memory: 18384kb

input:

2 2
0 1
0 1
1 1

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1

result:

ok 3 lines

Test #2:

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

input:

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

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
0
1
1

result:

ok 6 lines

Test #3:

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

input:

5000 5000
4000 193
193 3720
3720 2830
2830 1679
2830 3875
193 246
3720 2628
3720 2220
2220 749
2628 1622
1622 3105
4000 1742
193 1747
1622 1813
749 1537
3875 3418
1537 605
2220 3355
3418 2032
749 4629
4000 1787
4000 4981
1787 2204
246 938
2220 1576
4981 1872
938 3286
2032 4873
3875 2348
2204 654
193...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
26
27
27
28
28
29
29
29
30
30
31
31
32
32
32
33
33
34
34
35
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
43
44
44
...

result:

wrong answer 138th lines differ - expected: '61', found: '62'

Subtask #2:

score: 16
Accepted

Test #12:

score: 16
Accepted
time: 57ms
memory: 30156kb

input:

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

output:

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

result:

ok 200001 lines

Test #13:

score: 16
Accepted
time: 63ms
memory: 29168kb

input:

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

output:

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

result:

ok 200001 lines

Test #14:

score: 16
Accepted
time: 64ms
memory: 29940kb

input:

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

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
2
3
3
4
4
4
5
5
5
5
5
6
7
8
8
9
9
10
10
10
10
10
10
10
11
12
13
13
13
13
14
15
15
16
16
17
18
18
19
20
20
21
21
21
21
22
23
23
23
23
24
24
24
25
26
26
26
27
27
28
28
29
29
30
31
31
32
32
33
33
34
35
36
36
...

result:

ok 200001 lines

Test #15:

score: 16
Accepted
time: 55ms
memory: 29360kb

input:

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

output:

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

result:

ok 200001 lines

Test #16:

score: 16
Accepted
time: 62ms
memory: 29264kb

input:

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

output:

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

result:

ok 200001 lines

Test #17:

score: 16
Accepted
time: 118ms
memory: 29996kb

input:

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

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
3
3
4
4
5
6
6
7
7
8
7
7
7
8
8
9
8
8
8
8
8
8
8
8
8
7
7
7
7
6
6
6
6
6
5
5
5
5
5
5
5
5
5
5
5
5
4
4
4
4
4
4
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2...

result:

ok 200001 lines

Test #18:

score: 16
Accepted
time: 108ms
memory: 29168kb

input:

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

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
0
0
1
1
1
1
1
0
0
0
0
0
1
2
3
3
3
3
3
3
3
4
4
5
5
5
6
7
7
7
7
7
8
7
8
8
7
7
7
7
7
7
7
7
7
6
6
5
5
5
5
5
5
5
5
5
5
5
5
5
4
4
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3...

result:

ok 200001 lines

Test #19:

score: 16
Accepted
time: 109ms
memory: 29428kb

input:

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

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #20:

score: 16
Accepted
time: 59ms
memory: 28712kb

input:

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

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #21:

score: 16
Accepted
time: 60ms
memory: 28516kb

input:

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

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #22:

score: 16
Accepted
time: 113ms
memory: 31104kb

input:

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

output:

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

result:

ok 200001 lines

Test #23:

score: 16
Accepted
time: 108ms
memory: 29300kb

input:

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

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
1
1
1
1
1
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
4
5
4
4
4
4
4
5
6
7
7
6
7
8
8
8
8
8
8
8
8
8
9
8
8
9
9
10
10
11
10
10
10
10
10
10
11
10
10
10
10
10
10
10
10
11
11
12
13
14
14
14
14
14
15
16
17
17
17
17
17
18
18
18
17
17
17
17
18
18
19
19
20
21
22
22
22
22
22
22
23
23
...

result:

ok 200001 lines

Test #24:

score: 16
Accepted
time: 104ms
memory: 29168kb

input:

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

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Subtask #3:

score: 0
Wrong Answer

Test #25:

score: 20
Accepted
time: 75ms
memory: 29800kb

input:

200000 200000
155284 18435
18435 57260
57260 88628
88628 170108
57260 126961
170108 72596
72596 46044
170108 28914
46044 177699
155284 143087
18435 161808
177699 107693
18435 74517
28914 77075
126961 116303
177699 26806
74517 43330
77075 188898
126961 45168
57260 93201
93201 198698
77075 36077
57260...

output:

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

result:

ok 200001 lines

Test #26:

score: 20
Accepted
time: 75ms
memory: 27680kb

input:

200000 200000
20214 166890
166890 39782
39782 160973
160973 71809
71809 84135
84135 193485
193485 191907
191907 73443
73443 172846
172846 62828
62828 30539
30539 148834
148834 105784
105784 31379
31379 169920
169920 104347
104347 46092
46092 84919
84919 105144
105144 181794
181794 12834
12834 103965...

output:

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

result:

ok 200001 lines

Test #27:

score: 20
Accepted
time: 71ms
memory: 30140kb

input:

200000 200000
13661 52989
13661 191413
13661 183385
13661 180760
13661 45914
13661 154223
13661 92602
13661 143465
13661 115429
13661 35411
13661 110883
13661 100122
13661 103685
13661 173658
13661 44682
13661 142827
13661 182193
13661 191182
13661 101940
13661 117063
13661 92502
13661 128744
13661 ...

output:

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

result:

ok 200001 lines

Test #28:

score: 0
Wrong Answer
time: 79ms
memory: 29480kb

input:

200000 200000
59493 126128
59493 29185
29185 51986
126128 194222
194222 36489
29185 13257
59493 88509
29185 5290
88509 117426
88509 9059
117426 14322
88509 79181
14322 145100
59493 177676
36489 59023
14322 107337
107337 91882
59023 62581
88509 79723
62581 111878
88509 99587
107337 50973
107337 72208...

output:

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

result:

wrong answer 33139th lines differ - expected: '16556', found: '16557'

Subtask #4:

score: 0
Wrong Answer

Test #37:

score: 23
Accepted
time: 122ms
memory: 30076kb

input:

200000 200000
124028 117993
117993 64181
124028 176900
64181 197782
124028 153477
153477 179542
64181 191368
197782 55523
64181 36078
153477 108486
117993 169125
179542 68449
124028 153826
124028 142937
36078 65258
36078 28508
68449 114673
191368 17655
197782 90991
176900 48570
191368 6324
153826 18...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #38:

score: 23
Accepted
time: 136ms
memory: 28712kb

input:

200000 200000
131866 18043
18043 57193
57193 60655
60655 35995
35995 28070
28070 67968
67968 105408
105408 156686
156686 106458
106458 29522
29522 122097
122097 74460
74460 184393
184393 103127
103127 66034
66034 143537
143537 21725
21725 50976
50976 176162
176162 105552
105552 55780
55780 62169
621...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #39:

score: 23
Accepted
time: 105ms
memory: 31336kb

input:

200000 200000
151691 17854
151691 146833
151691 26054
151691 187921
151691 87998
151691 15359
151691 105393
151691 139556
151691 144598
151691 19426
151691 72223
151691 81216
151691 4463
151691 198983
151691 82874
151691 131724
151691 76749
151691 167757
151691 4589
151691 60837
151691 117757
151691...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #40:

score: 0
Wrong Answer
time: 130ms
memory: 29680kb

input:

200000 200000
57103 151863
57103 65099
65099 131631
131631 104062
131631 193083
104062 5074
65099 80436
80436 44079
57103 40438
193083 5819
5074 88154
65099 77383
77383 82202
193083 96604
104062 174500
80436 76033
80436 152882
104062 196890
88154 128462
193083 78716
96604 167178
65099 52255
128462 1...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
9
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
1...

result:

wrong answer 1181st lines differ - expected: '9', found: '10'

Subtask #5:

score: 0
Wrong Answer

Test #51:

score: 0
Wrong Answer
time: 115ms
memory: 28972kb

input:

200000 200000
75490 97148
75490 176817
75490 80168
75490 73425
97148 38334
80168 199950
73425 5116
5116 154439
80168 90246
154439 5305
154439 101118
101118 28211
90246 91284
75490 103069
80168 85099
176817 55430
38334 31693
55430 28292
80168 163565
163565 196782
28211 194198
28292 163487
73425 30097...

output:

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

result:

wrong answer 100012th lines differ - expected: '49997', found: '49998'
English 繁體中文 简体中文

Server Time: 2025-04-09 19:49:17 | OpenSource Project