CSES - IZhO 2017, day 2 - Results
Submission details
Task:Hard route
Sender:Lieska
Submission time:2019-02-09 14:34:26 +0200
Language:C++
Status:READY
Result:19
Feedback
groupverdictscore
#1ACCEPTED19
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.02 s1, 2, 3details
#3ACCEPTED0.02 s1, 2, 3details
#4ACCEPTED0.02 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.02 s1, 2, 3details
#7ACCEPTED0.03 s1, 2, 3details
#8ACCEPTED0.03 s1, 2, 3details
#9ACCEPTED0.02 s1, 2, 3details
#10ACCEPTED0.02 s1, 2, 3details
#11ACCEPTED0.04 s1, 2, 3details
#12ACCEPTED0.05 s1, 2, 3details
#13ACCEPTED0.05 s1, 2, 3details
#14ACCEPTED0.04 s1, 2, 3details
#15ACCEPTED0.02 s1, 2, 3details
#16ACCEPTED0.02 s1, 2, 3details
#17ACCEPTED0.02 s1, 2, 3details
#18ACCEPTED0.01 s1, 2, 3details
#19ACCEPTED0.02 s1, 2, 3details
#20ACCEPTED0.01 s1, 2, 3details
#21ACCEPTED0.01 s1, 2, 3details
#22ACCEPTED0.02 s1, 2, 3details
#23ACCEPTED0.02 s1, 2, 3details
#24ACCEPTED0.10 s1, 2, 3details
#25--2, 3details
#26--2, 3details
#27--2, 3details
#28--2, 3details
#29--2, 3details
#30--2, 3details
#31--2, 3details
#32--2, 3details
#33--2, 3details
#34--2, 3details
#35--2, 3details
#36--2, 3details
#37--2, 3details
#38--2, 3details
#39--2, 3details
#40--2, 3details
#41--2, 3details
#42--2, 3details
#43--2, 3details
#44--2, 3details
#45--2, 3details
#46--2, 3details
#47--2, 3details
#48--2, 3details
#490.02 s3details
#500.02 s3details
#510.01 s3details
#520.03 s3details
#530.02 s3details
#540.02 s3details
#550.01 s3details
#560.01 s3details
#570.02 s3details
#580.01 s3details
#590.03 s3details
#600.01 s3details
#610.01 s3details
#620.01 s3details
#630.01 s3details
#640.02 s3details
#650.01 s3details
#660.01 s3details
#670.02 s3details
#680.03 s3details
#690.02 s3details
#700.02 s3details
#710.02 s3details
#720.02 s3details
#730.02 s3details
#740.02 s3details
#750.02 s3details
#760.03 s3details
#770.01 s3details
#780.01 s3details

Code

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, a, b, s, q;
    multiset<int> p;
    cin >> n;
    int v[n+1][n+1]={};
    for (int i=1; i<n; ++i){
        cin >> a >> b;
        v[a][b]=1;
        v[b][a]=1;
    }
    int t[n+1]={}, r[n+1]={};
    for (int i=1; i<=n; ++i){
        s=0;
        for (int j=1; j<=n; ++j) {
            if (v[i][j]) ++s;
        }
        if (s==1) t[i]=1;
    }
    int e[n+1][n+1];
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=n; ++j){
            if (i==j) e[i][j]=0;
            else if (v[i][j]) e[i][j]=1;
            else e[i][j]=1e6;
        }
    }
    for (int k=1; k<=n; ++k){
        for (int i=1; i<=n; ++i){
            for (int j=1; j<=n; ++j){
                e[i][j]=min(e[i][j], e[i][k]+e[k][j]);
            }
        }
    }
    for (int i=1; i<=n; ++i){
        if (t[i]){
            for (int j=i; j<=n; ++j){
                if (j>i && t[j]){
                    for (int k=1; k<=n; ++k) r[k]=0;
                    for (int k=1; k<=n; ++k){
                        if (e[i][k]+e[j][k]==e[i][j] && i!=k && j!=k) r[k]=1;
                    }
                    s=0;
                    for (int k=1; k<=n; ++k){
                        q=1e6;
                        if (k!=i && k!=j && r[k]==0){
                            for (int l=1; l<=n; ++l){
                                if (r[l]==1){
                                    if (e[k][l]<q) q=e[k][l];
                                }
                            }
                        }
                        if (q>s && q<1e6) s=q;
                    }
                    p.insert(e[i][j]*s);
                }
            }
        }
    }
    auto it=p.end();
    it--;
    cout << *it << " " << p.count(*it);
    return 0;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
7
1 2
1 3
2 4
2 5
...

correct output
6 2

user output
6 2

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
4
1 2
2 3
2 4

correct output
2 3

user output
2 3

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
5
1 2
2 3
3 4
4 5

correct output
0 1

user output
0 1

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
2 1
3 1

correct output
0 1

user output
0 1

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
1 2
2 3

correct output
0 1

user output
0 1

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
1 2

correct output
0 1

user output
0 1

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
11 34
11 30
30 89
89 61
...

correct output
510 9

user output
510 9

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
84 10
10 46
46 41
84 14
...

correct output
624 1

user output
624 1

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
15 27
15 73
15 49
27 61
...

correct output
624 2

user output
624 2

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
41 49
41 2
49 5
49 87
...

correct output
510 5

user output
510 5

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
60 4
60 99
99 8
99 51
...

correct output
676 2

user output
676 2

Test 12

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
21 54
21 51
51 42
51 46
...

correct output
676 2

user output
676 2

Test 13

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
43 96
43 99
99 100
99 87
...

correct output
676 2

user output
676 2

Test 14

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
89 92
89 61
61 18
61 32
...

correct output
676 2

user output
676 2

Test 15

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
14 46
46 42
42 57
57 71
...

correct output
1836 1

user output
1836 1

Test 16

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
11 15
15 100
100 70
70 92
...

correct output
1836 1

user output
1836 1

Test 17

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
22 66
66 72
72 20
20 80
...

correct output
1836 1

user output
1836 1

Test 18

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
19 70
70 11
11 92
92 14
...

correct output
1836 1

user output
1836 1

Test 19

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
100 42
36 11
20 93
58 27
...

correct output
0 1

user output
0 1

Test 20

Group: 1, 2, 3

Verdict: ACCEPTED

input
99
71 50
32 52
3 67
54 89
...

correct output
0 1

user output
0 1

Test 21

Group: 1, 2, 3

Verdict: ACCEPTED

input
97
86 30
35 43
24 46
67 28
...

correct output
1152 6

user output
1152 6

Test 22

Group: 1, 2, 3

Verdict: ACCEPTED

input
96
9 10
76 49
51 21
49 30
...

correct output
722 10

user output
722 10

Test 23

Group: 1, 2, 3

Verdict: ACCEPTED

input
92
46 14
70 32
2 73
85 92
...

correct output
98 78

user output
98 78

Test 24

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
84 77
38 77
77 93
77 18
...

correct output
2 4851

user output
2 4851

Test 25

Group: 2, 3

Verdict:

input
5000
108 1090
1090 116
108 2557
108 790
...

correct output
77624 1

user output
(empty)

Test 26

Group: 2, 3

Verdict:

input
5000
1726 3190
3190 4781
4781 2577
1726 1933
...

correct output
75180 3

user output
(empty)

Test 27

Group: 2, 3

Verdict:

input
5000
238 3015
238 3788
3015 763
238 3952
...

correct output
67689 3

user output
(empty)

Test 28

Group: 2, 3

Verdict:

input
5000
3811 1893
3811 792
3811 3788
3811 4838
...

correct output
75030 3

user output
(empty)

Test 29

Group: 2, 3

Verdict:

input
5000
168 3267
168 4697
4697 4099
4697 4154
...

correct output
1565001 2

user output
(empty)

Test 30

Group: 2, 3

Verdict:

input
5000
3018 2323
3018 1644
1644 3826
1644 4180
...

correct output
1565001 2

user output
(empty)

Test 31

Group: 2, 3

Verdict:

input
5000
1832 3776
1832 4436
4436 1337
4436 567
...

correct output
1565001 2

user output
(empty)

Test 32

Group: 2, 3

Verdict:

input
5000
1991 3088
1991 1990
1990 2727
1990 2434
...

correct output
1565001 2

user output
(empty)

Test 33

Group: 2, 3

Verdict:

input
5000
3243 2207
2207 438
438 2783
2783 2291
...

correct output
4686874 1

user output
(empty)

Test 34

Group: 2, 3

Verdict:

input
5000
4248 2685
2685 175
175 1190
1190 2024
...

correct output
4686874 1

user output
(empty)

Test 35

Group: 2, 3

Verdict:

input
5000
2112 1534
1534 1558
1558 2262
2262 1975
...

correct output
4686874 1

user output
(empty)

Test 36

Group: 2, 3

Verdict:

input
5000
1235 1454
1454 1062
1062 1744
1744 1205
...

correct output
4686874 1

user output
(empty)

Test 37

Group: 2, 3

Verdict:

input
5000
560 803
899 2803
1090 1035
2285 3211
...

correct output
0 1

user output
(empty)

Test 38

Group: 2, 3

Verdict:

input
4999
1383 1758
1838 1884
2107 2408
3122 4088
...

correct output
0 1

user output
(empty)

Test 39

Group: 2, 3

Verdict:

input
4996
801 2061
2383 3017
373 355
840 3390
...

correct output
1996002 10

user output
(empty)

Test 40

Group: 2, 3

Verdict:

input
4991
3918 3416
1976 3997
224 3763
3172 1918
...

correct output
498002 45

user output
(empty)

Test 41

Group: 2, 3

Verdict:

input
4981
60 2930
1298 4348
1072 4876
4723 4797
...

correct output
124002 190

user output
(empty)

Test 42

Group: 2, 3

Verdict:

input
4951
3627 2151
3944 2165
4490 1736
523 2250
...

correct output
19602 1225

user output
(empty)

Test 43

Group: 2, 3

Verdict:

input
4901
1370 139
1739 2587
4146 1261
2596 593
...

correct output
4802 4950

user output
(empty)

Test 44

Group: 2, 3

Verdict:

input
4801
179 2101
3727 3495
1902 2186
1615 2717
...

correct output
1152 19900

user output
(empty)

Test 45

Group: 2, 3

Verdict:

input
4501
2688 2899
1416 818
1286 172
2063 3468
...

correct output
162 124750

user output
(empty)

Test 46

Group: 2, 3

Verdict:

input
4001
918 3204
3346 1093
1424 2131
461 988
...

correct output
32 499500

user output
(empty)

Test 47

Group: 2, 3

Verdict:

input
4801
3830 1737
2705 4747
3609 1236
4010 3243
...

correct output
8 2878800

user output
(empty)

Test 48

Group: 2, 3

Verdict:

input
5000
1229 3771
3771 722
3625 3771
1466 3771
...

correct output
2 12492501

user output
(empty)

Test 49

Group: 3

Verdict:

input
500000
389924 57822
57822 217726
57822 139251
389924 399958
...

correct output
13000624 8

user output
(empty)

Test 50

Group: 3

Verdict:

input
500000
118786 47756
47756 169958
118786 446268
47756 148195
...

correct output
14000392 7

user output
(empty)

Test 51

Group: 3

Verdict:

input
500000
129573 222254
222254 126962
222254 118174
126962 228147
...

correct output
13250477 3

user output
(empty)

Test 52

Group: 3

Verdict:

input
500000
161686 403260
161686 255571
161686 38129
161686 471358
...

correct output
13000260 8

user output
(empty)

Test 53

Group: 3

Verdict:

input
500000
211000 360323
211000 25161
25161 410825
25161 228266
...

correct output
15625250001 2

user output
(empty)

Test 54

Group: 3

Verdict:

input
500000
229975 245878
229975 381069
381069 235752
381069 281659
...

correct output
15625250001 2

user output
(empty)

Test 55

Group: 3

Verdict:

input
500000
339362 207756
339362 329523
329523 104875
329523 406705
...

correct output
15625250001 2

user output
(empty)

Test 56

Group: 3

Verdict:

input
500000
177180 20224
177180 489549
489549 272251
489549 366798
...

correct output
15625250001 2

user output
(empty)

Test 57

Group: 3

Verdict:

input
500000
441050 365574
365574 260480
260480 489676
489676 475065
...

correct output
46874937499 1

user output
(empty)

Test 58

Group: 3

Verdict:

input
500000
441371 336553
336553 486568
486568 295839
295839 244926
...

correct output
46874937499 1

user output
(empty)

Test 59

Group: 3

Verdict:

input
500000
140194 178993
178993 120975
120975 81556
81556 124409
...

correct output
46874937499 1

user output
(empty)

Test 60

Group: 3

Verdict:

input
500000
476177 228555
228555 180476
180476 183974
183974 333290
...

correct output
46874937499 1

user output
(empty)

Test 61

Group: 3

Verdict:

input
500000
470750 387879
417836 311762
342966 141634
406354 25179
...

correct output
0 1

user output
(empty)

Test 62

Group: 3

Verdict:

input
499999
494831 301936
134173 372968
341642 209941
69019 60029
...

correct output
0 1

user output
(empty)

Test 63

Group: 3

Verdict:

input
499996
458465 327411
334721 342076
281173 482634
174786 302877
...

correct output
19999600002 10

user output
(empty)

Test 64

Group: 3

Verdict:

input
499991
469217 60234
337422 32098
391126 410047
250380 490453
...

correct output
4999800002 45

user output
(empty)

Test 65

Group: 3

Verdict:

input
499981
86341 52816
87685 124628
264008 93843
215407 204482
...

correct output
1249900002 190

user output
(empty)

Test 66

Group: 3

Verdict:

input
499951
173074 102553
4605 467972
179848 239784
41864 483920
...

correct output
199960002 1225

user output
(empty)

Test 67

Group: 3

Verdict:

input
499901
331534 159654
354263 417447
456398 336456
145925 93463
...

correct output
49980002 4950

user output
(empty)

Test 68

Group: 3

Verdict:

input
499801
316655 31406
375271 253377
207046 406296
261469 73474
...

correct output
12490002 19900

user output
(empty)

Test 69

Group: 3

Verdict:

input
499501
181530 1562
425296 130234
77519 429847
246899 62810
...

correct output
1996002 124750

user output
(empty)

Test 70

Group: 3

Verdict:

input
499001
119240 366053
80890 350931
299626 85851
452737 458125
...

correct output
498002 499500

user output
(empty)

Test 71

Group: 3

Verdict:

input
497752
249959 43805
53866 407731
480579 76517
310033 271411
...

correct output
124002 1997001

user output
(empty)

Test 72

Group: 3

Verdict:

input
499801
311 302621
77322 218171
439178 122797
52421 371940
...

correct output
80000 3121251

user output
(empty)

Test 73

Group: 3

Verdict:

input
499951
15992 79636
154669 481782
18867 429430
314460 363528
...

correct output
5000 49985001

user output
(empty)

Test 74

Group: 3

Verdict:

input
499976
119557 332930
223497 192866
12074 112412
294767 451558
...

correct output
1250 199970001

user output
(empty)

Test 75

Group: 3

Verdict:

input
499991
420903 56414
2049 265308
289486 285688
134149 205864
...

correct output
200 1249925001

user output
(empty)

Test 76

Group: 3

Verdict:

input
499996
470165 235699
439599 455312
471414 301440
133301 186718
...

correct output
50 4999850001

user output
(empty)

Test 77

Group: 3

Verdict:

input
499999
354863 105878
6441 294653
154672 62081
62081 336952
...

correct output
8 31249625001

user output
(empty)

Test 78

Group: 3

Verdict:

input
500000
465618 25628
465618 443811
320366 465618
465618 382392
...

correct output
2 124999250001

user output
(empty)