QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#433050#3100. Meetings 2snpmrnhlol20 709ms60944kbC++143.5kb2024-06-07 22:58:242024-06-07 22:58:26

Judging History

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

  • [2024-06-07 22:58:26]
  • 评测
  • 测评结果：20
  • 用时：709ms
  • 内存：60944kb
查看
  • [2024-06-07 22:58:24]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
const int inf = 2e9;
vector <int> e[N];
int bad[N];
int sub[N];
int gbsub[N];
int pr[N];
int ans[N + 1];
int n;
void dfs(int node, int p){
    gbsub[node] = 1;
    pr[node] = p;
    for(auto i:e[node]){
        if(i == p)continue;
        dfs(i,node);
        gbsub[node]+=gbsub[i];
    }
}
int get(int node, int p){
    if(pr[node] == p){
        return gbsub[node];
    }else{
        return n - gbsub[p];
    }
}
void cendecomp(int node){
    vector <array<int,3>> nodes;
    int sz = 0;
    int cen = -1,cennr = inf;
    auto dfs = [&](auto self, int node, int p) -> void{
        sz++;
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node);
        }
    };
    auto dfs2 = [&](auto self, int node, int p) -> void{
        sub[node] = 1;
        int mx = -1;
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node);
            sub[node]+=sub[i];
            mx = max(mx,sub[i]);
        }
        mx = max(mx,sz - sub[node]);
        if(mx < cennr){
            mx = cennr;
            cen = node;
        }
    };
    auto dfs3 = [&](auto self, int node, int p, int dpth, int orig) -> void{
        int nr = min(get(node,p),get(cen,orig));
        ans[2*nr] = max(dpth,ans[2*nr]);
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node, dpth + 1, orig);
        }
    };
    auto dfs4 = [&](auto self, int node, int p, int dpth, int orig) -> void{
        nodes.push_back({orig,dpth,get(node,p)});
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node, dpth + 1, orig);
        }
    };
    dfs(dfs, node, -1);
    dfs2(dfs2, node, -1);
    for(auto i:e[cen]){
        if(bad[i])continue;
        dfs3(dfs3, i, cen, 2, i);
        dfs4(dfs4, i, cen, 1, i);
    }
    sort(nodes.begin(),nodes.end(),[&](auto a,auto b){
         return a[2] > b[2];
    });
    array <int,3> best[2] = {{-1,-1,-1},{-1,-1,-1}};
    for(int i = 0;i < nodes.size();i++){
        bool ok = 0;
        for(int j = 0;j < 2;j++){
            if(best[j][2] != -1 && nodes[i][2] != -1 && nodes[i][0] != best[j][0]){
                ans[2*nodes[i][2]] = max(ans[2*nodes[i][2]],nodes[i][1] + best[j][1] + 1);
            }
            if(best[j][0] == nodes[i][0]){
                best[j][1] = max(best[j][1],nodes[i][1]);
                if(best[1][1] > best[0][1])swap(best[0],best[1]);
                ok = 1;
            }
        }
        if(!ok){
            if(best[0][1] < nodes[i][1]){
                best[1] = best[0];
                best[0] = nodes[i];
            }else if(best[1][1] < nodes[i][1]){
                best[1] = nodes[i];
            }
        }
    }
    bad[cen] = 1;
    for(auto i:e[cen]){
        if(bad[i])continue;
        cendecomp(i);
    }
}
void solve(){
    cin>>n;
    for(int i = 0;i < n - 1;i++){
        int u,w;
        cin>>u>>w;
        u--;w--;
        e[w].push_back(u);
        e[u].push_back(w);
    }
    dfs(0, -1);
    cendecomp(0);
    for(int i = n;i >= 2;i--){
        if(i%2 == 0)ans[i] = max(ans[i],ans[i + 2]);
    }
    for(int i = 1;i <= n;i++){
        if(i%2 == 1)cout<<1<<'\n';
        else{
            cout<<max(ans[i],1)<<'\n';
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--)solve();
    return 0;
}
源文件, 语言: C++14

详细

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 0ms
memory: 8536kb

input:

1

output:

1

result:

ok single line: '1'

Test #2:

score: 4
Accepted
time: 0ms
memory: 8248kb

input:

2
2 1

output:

1
2

result:

ok 2 lines

Test #3:

score: 4
Accepted
time: 2ms
memory: 8304kb

input:

3
1 3
3 2

output:

1
3
1

result:

ok 3 lines

Test #4:

score: 4
Accepted
time: 3ms
memory: 8252kb

input:

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

output:

1
7
1
5
1
3
1
3
1
2
1
2
1
2

result:

ok 14 lines

Test #5:

score: 4
Accepted
time: 0ms
memory: 8256kb

input:

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

output:

1
8
1
6
1
5
1
4
1
2
1
1
1
1

result:

ok 14 lines

Test #6:

score: 4
Accepted
time: 0ms
memory: 8532kb

input:

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

output:

1
8
1
6
1
5
1
4
1
2
1
1
1
1

result:

ok 14 lines

Test #7:

score: 4
Accepted
time: 0ms
memory: 8248kb

input:

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

output:

1
7
1
5
1
3
1
2
1
2
1
1
1
1

result:

ok 14 lines

Test #8:

score: 4
Accepted
time: 2ms
memory: 8552kb

input:

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

output:

1
8
1
6
1
4
1
4
1
3
1
2
1
1
1

result:

ok 15 lines

Test #9:

score: 4
Accepted
time: 0ms
memory: 8252kb

input:

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

output:

1
8
1
6
1
4
1
4
1
2
1
2
1
2
1
2

result:

ok 16 lines

Test #10:

score: 4
Accepted
time: 0ms
memory: 8264kb

input:

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

output:

1
10
1
8
1
6
1
4
1
4
1
4
1
2
1
2

result:

ok 16 lines

Test #11:

score: 4
Accepted
time: 3ms
memory: 8244kb

input:

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

output:

1
7
1
5
1
5
1
3
1
3
1
3
1
2
1
1

result:

ok 16 lines

Test #12:

score: 4
Accepted
time: 2ms
memory: 8324kb

input:

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

output:

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

result:

ok 16 lines

Test #13:

score: 4
Accepted
time: 0ms
memory: 8252kb

input:

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

output:

1
9
1
7
1
5
1
5
1
4
1
3
1
3
1
2

result:

ok 16 lines

Test #14:

score: 4
Accepted
time: 2ms
memory: 8528kb

input:

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

output:

1
10
1
8
1
6
1
4
1
3
1
2
1
1

result:

ok 14 lines

Test #15:

score: 4
Accepted
time: 2ms
memory: 8252kb

input:

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

output:

1
14
1
12
1
10
1
8
1
6
1
4
1
2

result:

ok 14 lines

Test #16:

score: 4
Accepted
time: 2ms
memory: 8464kb

input:

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

output:

1
5
1
3
1
1
1
1
1
1
1
1
1
1
1

result:

ok 15 lines

Test #17:

score: 4
Accepted
time: 0ms
memory: 8476kb

input:

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

output:

1
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 16 lines

Test #18:

score: 4
Accepted
time: 2ms
memory: 8328kb

input:

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

output:

1
8
1
6
1
5
1
4
1
2
1
1
1
1
1
1

result:

ok 16 lines

Test #19:

score: 4
Accepted
time: 2ms
memory: 8480kb

input:

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

output:

1
6
1
4
1
3
1
2
1
2
1
2
1
2
1

result:

ok 15 lines

Test #20:

score: 4
Accepted
time: 0ms
memory: 8332kb

input:

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

output:

1
7
1
5
1
3
1
3
1
2
1
2
1
2
1
2

result:

ok 16 lines

Test #21:

score: 4
Accepted
time: 0ms
memory: 8360kb

input:

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

output:

1
7
1
5
1
3
1
2
1
2
1
2
1
2
1

result:

ok 15 lines

Subtask #2:

score: 16
Accepted

Dependency #1:

100%
Accepted

Test #22:

score: 16
Accepted
time: 8ms
memory: 8676kb

input:

3985
2388 2281
2388 3669
2448 3669
2448 2962
3147 2448
2166 2388
209 3147
2325 2388
1584 3147
1349 3669
3525 3147
2962 2698
1349 660
2281 553
3454 3147
2325 3651
3339 2281
2281 3565
1584 1621
1584 2118
819 3339
72 2166
2025 660
553 2331
3266 209
2166 2930
2432 3454
3677 3525
368 1349
553 519
3677 28...

output:

1
34
1
32
1
31
1
30
1
29
1
28
1
28
1
28
1
28
1
27
1
27
1
27
1
27
1
27
1
27
1
27
1
26
1
26
1
25
1
25
1
24
1
24
1
23
1
23
1
23
1
23
1
22
1
22
1
22
1
22
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
19
1
19
1
19
1
19
1
19
1
19
1
19
1
19
1
19
1
19
1
18
1
18
1
18
1
18
1
18
...

result:

ok 3985 lines

Test #23:

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

input:

3986
1021 3515
726 1021
757 1021
1483 1021
483 1483
3239 483
1021 2531
757 1622
483 2480
90 1622
483 3977
90 3459
757 1821
761 3239
3022 757
726 669
2327 90
3585 3022
279 3977
3977 2484
846 1622
1021 2639
2754 3515
1176 1021
96 483
3585 3604
2327 1741
2327 1759
2480 2457
2327 306
3977 3422
1233 3977...

output:

1
35
1
33
1
31
1
29
1
29
1
28
1
28
1
28
1
26
1
26
1
26
1
25
1
24
1
24
1
24
1
24
1
24
1
24
1
23
1
23
1
23
1
22
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
19
1
19
1
19
1
19
1
19
1
19
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
...

result:

ok 3986 lines

Test #24:

score: 16
Accepted
time: 8ms
memory: 8672kb

input:

3942
2742 1586
1768 2742
1586 3325
1768 673
3166 673
1392 3166
1764 2742
3846 673
673 24
24 1880
3325 2461
180 24
2461 1825
1586 3232
369 3325
2322 24
180 1198
36 1825
1880 865
3625 865
3325 2289
3625 1318
1825 1393
1309 36
88 1768
36 570
2588 570
36 3621
3925 1764
1090 2742
674 570
180 3150
118 362...

output:

1
43
1
41
1
39
1
37
1
37
1
36
1
35
1
34
1
34
1
34
1
33
1
33
1
32
1
32
1
32
1
31
1
31
1
31
1
30
1
30
1
30
1
29
1
28
1
28
1
28
1
28
1
28
1
28
1
28
1
28
1
28
1
28
1
28
1
28
1
28
1
28
1
28
1
28
1
27
1
26
1
26
1
26
1
26
1
26
1
26
1
26
1
26
1
26
1
26
1
26
1
26
1
26
1
26
1
26
1
26
1
26
1
24
1
24
1
24
1
24
...

result:

ok 3942 lines

Test #25:

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

input:

3960
750 291
750 1350
2287 291
2287 1155
590 1350
1350 2483
590 2452
3626 291
291 249
2287 570
491 590
2491 1155
1155 870
1155 2397
750 259
491 3488
3488 1848
3107 750
705 3626
570 3649
3411 2397
2483 3770
1415 590
454 3488
2960 1350
259 2224
1415 648
2254 491
2864 705
249 1567
275 1350
2757 491
107...

output:

1
30
1
28
1
27
1
25
1
24
1
23
1
22
1
22
1
22
1
20
1
20
1
20
1
20
1
20
1
19
1
19
1
19
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
17
1
17
1
17
1
17
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
15
1
15
1
15
1
15
1
14
1
14
1
14
1
14
1
14
1
14
1
14
1
14
...

result:

ok 3960 lines

Test #26:

score: 16
Accepted
time: 8ms
memory: 8644kb

input:

3949
3764 3701
2864 3701
1554 3701
578 2864
3701 3539
3539 1974
3539 88
3701 1236
578 2111
3012 88
1895 3764
273 1236
1174 2864
222 578
1895 3149
3539 2629
3429 2111
1544 3429
1554 190
2069 2111
1236 3542
578 3658
2762 1974
3424 1895
1133 2762
3658 3527
1895 696
2721 2762
3539 452
88 3610
2721 3147
...

output:

1
31
1
29
1
29
1
27
1
26
1
26
1
25
1
24
1
24
1
24
1
23
1
23
1
22
1
21
1
21
1
21
1
21
1
21
1
21
1
20
1
19
1
19
1
19
1
19
1
19
1
19
1
19
1
19
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
16
1
16
1
16
1
15
1
14
1
14
1
14
1
14
1
14
1
14
1
14
1
13
1
13
1
13
...

result:

ok 3949 lines

Test #27:

score: 16
Accepted
time: 7ms
memory: 8676kb

input:

4000
3523 3550
3523 3231
1960 3523
308 3550
3766 1960
3638 3550
1398 308
308 172
3550 3214
3638 3212
1973 3231
448 172
3214 1726
2761 3550
1792 3212
1973 538
3231 1838
3491 2761
172 1551
2340 448
1484 2761
3214 2034
448 2208
189 3212
800 3550
3214 1033
189 1504
2051 3638
941 1726
1805 1398
230 538
3...

output:

1
34
1
32
1
31
1
29
1
29
1
28
1
27
1
26
1
26
1
26
1
26
1
26
1
25
1
25
1
25
1
24
1
24
1
24
1
24
1
24
1
22
1
22
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
20
1
19
1
19
1
19
1
19
1
19
1
19
1
19
1
19
1
19
1
19
1
18
1
18
1
18
1
18
1
18
...

result:

ok 4000 lines

Test #28:

score: 16
Accepted
time: 4ms
memory: 8688kb

input:

4000
2627 2898
2898 314
3345 2627
314 2466
3345 1095
3031 314
1095 2542
3074 2627
3391 3031
2898 89
3314 2898
3415 2898
2542 12
49 314
2361 314
2131 2361
3031 920
2131 2303
3074 368
3915 1095
565 12
89 284
2303 1975
2312 2466
2131 3901
3481 12
3712 2627
49 3860
350 2131
3031 3489
686 2361
3415 340
3...

output:

1
33
1
31
1
29
1
29
1
28
1
26
1
26
1
26
1
26
1
24
1
24
1
24
1
24
1
24
1
24
1
23
1
22
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
21
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
19
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
17
1
17
1
17
1
17
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
...

result:

ok 4000 lines

Test #29:

score: 16
Accepted
time: 3ms
memory: 8832kb

input:

4000
2089 2753
2753 1171
3685 2753
2089 584
2089 2113
2865 3685
2113 3150
1828 2089
2753 170
227 2089
157 2753
584 906
3150 2429
2113 2332
227 2972
227 1358
2478 906
2113 3791
170 273
1171 3846
1358 3727
2972 1844
1989 2865
3791 2995
2933 3685
1171 3992
584 682
2865 1771
256 3150
796 584
614 1844
27...

output:

1
31
1
29
1
27
1
26
1
26
1
26
1
25
1
25
1
24
1
24
1
23
1
23
1
23
1
22
1
22
1
20
1
19
1
18
1
18
1
18
1
18
1
18
1
18
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
15
1
15
1
15
1
15
1
15
1
15
1
15
1
15
1
15
1
15
1
15
1
15
1
15
1
14
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
...

result:

ok 4000 lines

Test #30:

score: 16
Accepted
time: 3ms
memory: 8836kb

input:

4000
3023 347
697 347
697 3559
3559 1639
3344 697
347 3237
2644 347
697 3054
64 3023
697 767
2417 2644
1993 3237
380 2417
140 3054
2900 1993
1483 3559
1515 3054
3395 2417
347 3304
697 2805
3559 3519
2644 196
3989 2417
2805 2464
1326 2417
2900 1703
2496 697
767 3098
790 196
954 1326
219 1639
790 31
3...

output:

1
32
1
30
1
28
1
27
1
26
1
26
1
24
1
24
1
23
1
23
1
23
1
22
1
22
1
22
1
21
1
21
1
20
1
20
1
20
1
20
1
19
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
17
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
15
1
15
1
15
1
15
1
15
1
15
1
15
1
15
1
15
1
15
1
15
1
15
...

result:

ok 4000 lines

Test #31:

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

input:

4000
609 943
2191 943
609 3385
3560 609
3385 3309
3278 609
609 3625
2260 2191
943 1008
1626 2191
2332 3278
1305 609
1386 3625
1008 503
3278 45
3309 1355
3222 3625
2260 3488
2547 3222
2260 1154
3385 2503
1038 3625
2503 3211
1305 2011
2332 3944
1355 190
2187 3385
2187 1252
3211 625
1843 3488
943 2650
...

output:

1
33
1
31
1
29
1
27
1
26
1
26
1
26
1
25
1
24
1
23
1
22
1
22
1
22
1
22
1
21
1
20
1
20
1
20
1
20
1
20
1
19
1
19
1
19
1
19
1
19
1
19
1
18
1
18
1
18
1
18
1
18
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
17
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
15
1
15
1
15
1
15
1
15
1
15
...

result:

ok 4000 lines

Test #32:

score: 16
Accepted
time: 139ms
memory: 37932kb

input:

3999
3551 1490
2942 1490
2942 2444
1082 2444
2671 1082
2671 500
500 316
3049 316
3049 3475
3515 3475
3515 982
982 2792
2792 1105
1105 3699
3699 506
651 506
2766 651
2766 2563
1176 2563
1176 430
1543 430
3814 1543
3814 2327
3925 2327
3925 2880
2880 2300
3098 2300
3098 2635
2635 3567
3567 2168
1216 21...

output:

1
2321
1
2319
1
2318
1
2318
1
2317
1
2316
1
2314
1
2313
1
2311
1
2311
1
2309
1
2308
1
2306
1
2304
1
2302
1
2301
1
2301
1
2299
1
2297
1
2297
1
2297
1
2297
1
2295
1
2294
1
2294
1
2293
1
2291
1
2289
1
2288
1
2287
1
2286
1
2286
1
2285
1
2285
1
2284
1
2284
1
2283
1
2282
1
2281
1
2279
1
2278
1
2277
1
2277...

result:

ok 3999 lines

Test #33:

score: 16
Accepted
time: 205ms
memory: 60944kb

input:

3999
3918 3738
3738 3159
3784 3159
3784 111
111 254
2011 254
2011 3528
439 3528
3108 439
3206 3108
2525 3206
2562 2525
653 2562
3387 653
2559 3387
1694 2559
1694 58
2863 58
2863 230
230 1722
3589 1722
3589 876
2498 876
2498 1843
1843 3798
3798 406
406 3467
464 3467
464 335
335 3457
3566 3457
3566 33...

output:

1
3999
1
3997
1
3995
1
3993
1
3991
1
3989
1
3987
1
3985
1
3983
1
3981
1
3979
1
3977
1
3975
1
3973
1
3971
1
3969
1
3967
1
3965
1
3963
1
3961
1
3959
1
3957
1
3955
1
3953
1
3951
1
3949
1
3947
1
3945
1
3943
1
3941
1
3939
1
3937
1
3935
1
3933
1
3931
1
3929
1
3927
1
3925
1
3923
1
3921
1
3919
1
3917
1
3915...

result:

ok 3999 lines

Test #34:

score: 16
Accepted
time: 4ms
memory: 8836kb

input:

3999
2214 374
374 2802
734 374
374 600
374 348
2277 374
374 672
374 3440
3264 374
374 3690
374 3344
374 884
2491 374
1489 374
374 3417
2379 374
374 2966
374 1772
374 1300
3835 374
374 1182
3615 374
1101 374
3854 374
2158 374
1485 374
374 1728
374 579
374 2092
2766 374
374 3159
3611 374
3258 374
374 ...

output:

1
14
1
12
1
11
1
11
1
9
1
8
1
7
1
6
1
4
1
4
1
3
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
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
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
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
...

result:

ok 3999 lines

Test #35:

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

input:

4000
2958 816
90 2958
2958 1232
2958 3524
14 2958
2958 3175
3375 2958
1924 2958
3815 2958
1291 2958
2958 3618
301 2958
2958 580
2958 3945
3851 2958
2958 2466
2958 2968
2958 1472
2958 2235
456 2958
2958 2654
2958 350
2958 274
2958 373
2958 2422
2958 3589
2958 1283
2958 2903
2658 2958
3980 2958
2958 1...

output:

1
3
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
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
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
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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 4000 lines

Test #36:

score: 16
Accepted
time: 22ms
memory: 11808kb

input:

4000
3280 1562
3962 3280
3962 3612
2987 3612
2987 1483
1483 453
453 1853
3554 1853
3349 3554
3349 3321
3321 2907
1224 2907
2835 1224
3372 2835
809 3372
809 2413
744 2413
3342 744
3342 2722
2722 3799
477 3799
1855 477
1855 3736
3736 2680
2680 499
499 2645
2645 1643
1643 426
690 426
690 560
560 2486
8...

output:

1
176
1
174
1
173
1
172
1
170
1
169
1
167
1
166
1
164
1
163
1
161
1
160
1
158
1
157
1
155
1
154
1
152
1
151
1
149
1
148
1
146
1
145
1
143
1
142
1
140
1
139
1
137
1
136
1
134
1
133
1
131
1
130
1
128
1
127
1
125
1
124
1
122
1
121
1
119
1
118
1
116
1
115
1
113
1
112
1
110
1
109
1
107
1
106
1
104
1
103
...

result:

ok 4000 lines

Test #37:

score: 16
Accepted
time: 4ms
memory: 8636kb

input:

4000
3203 2979
2436 2979
2635 2979
2020 2979
2979 962
1025 2979
3728 2979
531 2979
2979 847
2979 1896
2979 2707
2979 679
1720 2979
2979 2187
2979 2340
2740 2979
3023 2979
2979 2202
2979 3983
2979 3820
2979 31
2979 646
244 2979
2972 2979
2979 2605
831 2979
2979 2218
2979 41
2979 3840
635 2979
2979 21...

output:

1
30
1
28
1
27
1
26
1
25
1
24
1
24
1
24
1
24
1
24
1
24
1
24
1
24
1
24
1
24
1
24
1
24
1
24
1
24
1
23
1
22
1
21
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
20
1
19
1
18
1
17
1
16
1
16
1
16
1
16
...

result:

ok 4000 lines

Test #38:

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

input:

3999
1409 586
479 1409
3623 1409
3156 1409
1409 501
1409 230
1409 2776
1409 3132
1409 1130
1727 1409
1409 2829
1409 3176
1409 159
1409 3809
1409 1619
1409 811
2322 1409
3090 1409
2300 1409
1409 215
2407 1409
1409 1553
1409 659
3403 1409
2222 1409
1409 418
1409 98
1409 1238
1479 1409
1409 3883
3320 1...

output:

1
1999
1
1997
1
1995
1
1993
1
1991
1
1989
1
1987
1
1985
1
1983
1
1981
1
1979
1
1977
1
1975
1
1973
1
1971
1
1969
1
1967
1
1965
1
1963
1
1961
1
1959
1
1957
1
1955
1
1953
1
1951
1
1949
1
1947
1
1945
1
1943
1
1941
1
1939
1
1937
1
1935
1
1933
1
1931
1
1929
1
1927
1
1925
1
1923
1
1921
1
1919
1
1917
1
1915...

result:

ok 3999 lines

Subtask #3:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #39:

score: 80
Accepted
time: 610ms
memory: 45516kb

input:

196145
73351 68596
144883 68596
144883 77440
158554 77440
70653 73351
84095 77440
84095 107513
10720 73351
43180 77440
77440 172445
144883 18265
190722 10720
38486 84095
1238 68596
68596 53427
73990 70653
38486 182078
121987 190722
182693 190722
190722 22959
119892 68596
158028 144883
10720 49607
10...

output:

1
52
1
50
1
48
1
48
1
46
1
44
1
44
1
44
1
43
1
43
1
42
1
41
1
41
1
41
1
41
1
41
1
41
1
40
1
40
1
40
1
40
1
40
1
39
1
39
1
39
1
39
1
39
1
39
1
39
1
39
1
39
1
39
1
39
1
39
1
38
1
38
1
38
1
37
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
...

result:

ok 196145 lines

Test #40:

score: 80
Accepted
time: 488ms
memory: 35128kb

input:

192033
54553 30215
54553 185329
30215 133088
156207 54553
115933 133088
54553 63805
63805 139718
30215 2780
30215 191725
151837 2780
2780 93591
54553 59959
151837 14777
133088 171080
133088 178337
59959 40848
166838 185329
146753 178337
108283 93591
148600 171080
108283 190494
54553 60795
11272 1397...

output:

1
52
1
50
1
48
1
46
1
45
1
44
1
43
1
43
1
42
1
41
1
41
1
40
1
40
1
39
1
39
1
38
1
38
1
38
1
38
1
38
1
38
1
37
1
37
1
37
1
37
1
37
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
36
1
35
1
35
1
35
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
...

result:

ok 192033 lines

Test #41:

score: 80
Accepted
time: 540ms
memory: 42844kb

input:

196603
170388 25545
11159 25545
107159 11159
11159 80250
92811 170388
92811 8511
107159 153831
170388 109808
25545 105804
148259 92811
148259 158822
124605 92811
11159 63458
148259 41829
98276 158822
54562 148259
153831 45932
8511 177096
107159 135894
135894 144763
107159 182215
127686 124605
92811 ...

output:

1
51
1
49
1
47
1
46
1
45
1
44
1
44
1
43
1
43
1
43
1
43
1
42
1
42
1
41
1
40
1
40
1
39
1
39
1
39
1
39
1
38
1
38
1
38
1
38
1
37
1
37
1
37
1
35
1
35
1
35
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
34
1
33
1
33
1
33
1
33
1
33
1
33
1
33
1
33
1
33
1
33
1
33
...

result:

ok 196603 lines

Test #42:

score: 80
Accepted
time: 676ms
memory: 47420kb

input:

200000
195129 72334
196911 72334
10300 195129
72334 170139
296 10300
164032 170139
195129 191523
92869 72334
90499 195129
87804 170139
51382 87804
65650 191523
51382 161126
170139 34139
32880 170139
170139 37918
51383 296
198144 191523
86218 164032
65236 51382
34139 173213
38129 170139
195129 107166...

output:

1
52
1
50
1
48
1
48
1
47
1
46
1
46
1
46
1
46
1
45
1
45
1
45
1
44
1
44
1
43
1
43
1
43
1
43
1
42
1
42
1
42
1
40
1
40
1
40
1
40
1
40
1
39
1
39
1
39
1
39
1
39
1
39
1
39
1
39
1
38
1
38
1
38
1
38
1
38
1
38
1
38
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
36
1
36
1
36
1
36
...

result:

ok 200000 lines

Test #43:

score: 80
Accepted
time: 569ms
memory: 40252kb

input:

200000
51808 55920
51808 107133
99481 107133
48473 99481
107133 84201
169239 55920
45126 99481
169239 130080
48473 139103
34490 84201
34490 89448
198530 48473
84201 166142
98664 130080
51808 119149
3620 48473
45126 34483
176146 34483
50870 89448
83510 166142
89448 16525
81629 50870
79392 48473
85111...

output:

1
53
1
51
1
49
1
47
1
46
1
46
1
46
1
45
1
44
1
44
1
43
1
42
1
42
1
42
1
42
1
41
1
41
1
41
1
41
1
40
1
40
1
40
1
40
1
40
1
40
1
40
1
40
1
40
1
39
1
39
1
39
1
39
1
39
1
39
1
39
1
39
1
39
1
39
1
39
1
38
1
38
1
38
1
38
1
38
1
38
1
38
1
38
1
38
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
...

result:

ok 200000 lines

Test #44:

score: 80
Accepted
time: 709ms
memory: 52400kb

input:

200000
81667 85919
81667 48156
45385 85919
164235 45385
48156 40522
85919 158251
196015 40522
164235 132737
107652 158251
19736 132737
20724 158251
62404 40522
158251 83935
164235 189115
164235 149142
19736 162891
98222 83935
98222 112573
2181 164235
62404 65267
62404 161814
45385 127645
149142 2727...

output:

1
53
1
51
1
50
1
50
1
49
1
47
1
47
1
47
1
47
1
47
1
46
1
44
1
44
1
44
1
43
1
42
1
42
1
42
1
42
1
42
1
42
1
42
1
42
1
42
1
41
1
41
1
41
1
41
1
41
1
41
1
41
1
41
1
41
1
41
1
41
1
41
1
39
1
39
1
39
1
39
1
39
1
38
1
38
1
38
1
38
1
38
1
38
1
38
1
38
1
38
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
1
37
...

result:

ok 200000 lines

Test #45:

score: 0
Time Limit Exceeded

input:

199999
131003 152187
39261 131003
117174 39261
198536 117174
198536 195246
133452 195246
133452 154413
48622 154413
48622 8458
8458 140326
140326 100582
21675 100582
21675 132330
132330 143082
143082 67546
155514 67546
28153 155514
28153 139327
139327 152496
10461 152496
192620 10461
192620 51043
51...

output:

result:
English 繁體中文 简体中文

服务器时间: 2024-12-11 21:40:04 | 开源项目