CSES - Siperia opettaa 3.0 - Results
Submission details
Task:Toll Roads
Sender:zxc
Submission time:2016-07-29 15:52:18 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.06 sdetails
#3ACCEPTED0.05 sdetails
#4ACCEPTED0.05 sdetails
#5ACCEPTED0.06 sdetails
#6ACCEPTED0.05 sdetails
#7ACCEPTED0.05 sdetails
#8ACCEPTED0.06 sdetails
#9ACCEPTED0.06 sdetails
#10ACCEPTED0.05 sdetails
#11ACCEPTED0.05 sdetails
#12ACCEPTED0.05 sdetails
#13ACCEPTED0.05 sdetails
#14ACCEPTED0.06 sdetails
#15ACCEPTED0.06 sdetails
#16ACCEPTED0.05 sdetails
#17ACCEPTED0.05 sdetails
#18ACCEPTED0.06 sdetails
#19ACCEPTED0.06 sdetails
#20ACCEPTED0.06 sdetails
#21ACCEPTED0.06 sdetails
#22ACCEPTED0.05 sdetails
#23ACCEPTED0.06 sdetails
#24ACCEPTED0.06 sdetails
#25ACCEPTED0.05 sdetails
#26ACCEPTED0.06 sdetails
#27ACCEPTED0.06 sdetails
#280.05 sdetails
#290.06 sdetails
#300.27 sdetails
#310.74 sdetails
#320.73 sdetails
#330.72 sdetails
#340.81 sdetails
#351.72 sdetails
#361.83 sdetails
#371.83 sdetails
#381.82 sdetails
#391.84 sdetails
#401.83 sdetails
#410.06 sdetails
#420.06 sdetails
#430.20 sdetails
#440.78 sdetails
#450.78 sdetails
#460.80 sdetails
#470.79 sdetails
#480.88 sdetails
#491.96 sdetails
#501.90 sdetails
#511.95 sdetails
#521.94 sdetails
#531.94 sdetails
#540.06 sdetails
#550.06 sdetails
#560.33 sdetails
#570.56 sdetails
#580.55 sdetails
#590.65 sdetails
#601.25 sdetails
#611.48 sdetails
#621.22 sdetails
#631.35 sdetails
#641.52 sdetails
#651.58 sdetails
#661.24 sdetails
#67ACCEPTED2.08 sdetails
#68ACCEPTED0.76 sdetails
#69ACCEPTED0.94 sdetails
#70ACCEPTED0.52 sdetails
#71ACCEPTED0.05 sdetails
#72ACCEPTED0.06 sdetails

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int MN = 5555;;
vector<int> v[MN];
int pisin[MN];
int ha[MN];
bool used[MN];
int f1(int x) {
    used[x] = 1;
    pisin[x] = 0;
    ha[x] = 0;
    int q = 0;
    int w = 0;

    for(auto y: v[x]) {
	if(!used[y]) {
	    pisin[x] = max(pisin[x], f1(y)+1);
	    if(pisin[y]+1 > q) {
		w = q;
		q = pisin[y]+1;
	    }
	    else if(pisin[y]+1 > w) {
		w = pisin[y]+1;
	    }
	}
    }
    ha[x] = max(pisin[x], q+w);
    //cout<<x<<' '<<pisin[x]<<' '<<ha[x]<<'\n';
    return pisin[x];
}
pair<int, pair<int, pair<int, int> > > best = {1e9, {1e9, {0, 0}}};
int k;
void f2(int root, int x, int up, int d, int qwe) {
    if(d > k) return;
    used[x] = 1;
    int p1 = up;
    int p2 = 0;
    int p3 = 0;
    int h1 = qwe;
    int h2 = 0;
    for(auto y: v[x]) {
	if(!used[y]) {
	    if(ha[y] > h1) {
		h2 = h1;
		h1 =ha[y];
	    }
	    else if(ha[y] > h2) {
		h2 = ha[y];
	    }
	    if(pisin[y]+1 > p1) {
		p3 = p2;
		p2 = p1;
		p1 = pisin[y]+1;
	    }
	    else if(pisin[y]+1 > p2) {
		p3 = p2;
		p2 = pisin[y]+1;
	    }
	    else if(pisin[y]+1 > p3) {
		p3 = pisin[y]+1;
	    }
	}
    }
    //cout<<x<<' '<<p1<<' '<<p2<<' '<<p3<<"  "<<h1<<' '<<h2<<' '<<qwe<<'\n';
    int ma = pisin[x];
    ma = max(ma, p1 + p2);
    ma = max(ma, qwe);
    ma = max(ma, ha[x]);
    best = min(best, {ma, {d, {root, x}}});
    for(auto y: v[x]) {
	if(!used[y]) {
	    int nup = p1;
	    int nqwe = 0;
	    if(pisin[y]+1 == p1) {
		nqwe = max(qwe, p2+p3);
	    }
	    else if(pisin[y]+1 == p2) {
		nqwe = max(qwe, p1+p3);
	    }
	    else {
		nqwe = max(qwe, p1+p2);
	    }
	    int nha = h1;
	    if(ha[y] == nha) {
		nha = h2;
	    }
	    if(pisin[y]+1 == nup) {
		nup = p2;
	    }
	    f2(root, y, nup, d+1, max(nha, nqwe));
	}
    }
}
int main() {
    int n;
    cin>>n>>k;
    for(int i = 0; i< n-1; ++i) {
	int a,b;
	cin>>a>>b;
	v[a].push_back(b);
	v[b].push_back(a);
    }
    for(int i = 0; i < n; ++i) {
	memset(used, 0, sizeof used);
	f1(i);
	memset(used, 0, sizeof used);
	f2(i, i, 0, 0, 0);
    }
    cout<<best.F<<'\n';
    cout<<best.S.F<<'\n';
    if(best.S.F > 0) cout<<best.S.S.F<<' '<<best.S.S.S<<'\n';
}

Test details

Test 1

Verdict: ACCEPTED

input
8 3
0 2
0 5
2 3
5 1
...

correct output
2
3
2 6

user output
2
3
2 6

Test 2

Verdict: ACCEPTED

input
5 2
0 1
0 2
0 3
0 4

correct output
2
0

user output
2
0

Test 3

Verdict: ACCEPTED

input
2 1
0 1

correct output
0
1
0 1

user output
0
1
0 1

Test 4

Verdict: ACCEPTED

input
3 1
0 1
2 1

correct output
1
1
0 1

user output
1
1
0 1

Test 5

Verdict: ACCEPTED

input
3 1
0 2
1 2

correct output
1
1
0 2

user output
1
1
0 2

Test 6

Verdict: ACCEPTED

input
3 2
0 2
1 2

correct output
0
2
0 1

user output
0
2
0 1

Test 7

Verdict: ACCEPTED

input
4 1
0 3
0 1
3 2

correct output
2
1
0 3

user output
2
1
0 1

Test 8

Verdict: ACCEPTED

input
4 2
0 3
0 1
3 2

correct output
1
2
0 2

user output
1
2
0 2

Test 9

Verdict: ACCEPTED

input
4 3
0 3
0 1
3 2

correct output
0
3
1 2

user output
0
3
1 2

Test 10

Verdict: ACCEPTED

input
4 1
0 1
0 2
0 3

correct output
2
0

user output
2
0

Test 11

Verdict: ACCEPTED

input
4 2
0 1
0 2
0 3

correct output
1
2
1 2

user output
1
2
1 2

Test 12

Verdict: ACCEPTED

input
4 3
0 1
0 2
0 3

correct output
1
2
1 2

user output
1
2
1 2

Test 13

Verdict: ACCEPTED

input
6 3
0 1
0 2
0 3
2 4
...

correct output
2
2
2 3

user output
2
2
2 3

Test 14

Verdict: ACCEPTED

input
6 3
0 1
0 2
0 3
2 4
...

correct output
2
1
0 2

user output
2
1
0 2

Test 15

Verdict: ACCEPTED

input
8 5
0 1
1 2
2 3
0 4
...

correct output
2
4
2 5

user output
2
4
2 5

Test 16

Verdict: ACCEPTED

input
2 1
0 1

correct output
0
1
0 1

user output
0
1
0 1

Test 17

Verdict: ACCEPTED

input
3 1
2 1
0 2

correct output
1
1
0 2

user output
1
1
0 2

Test 18

Verdict: ACCEPTED

input
3 1
0 2
0 1

correct output
1
1
0 2

user output
1
1
0 1

Test 19

Verdict: ACCEPTED

input
3 2
1 0
1 2

correct output
0
2
0 2

user output
0
2
0 2

Test 20

Verdict: ACCEPTED

input
3 2
0 1
0 2

correct output
0
2
1 2

user output
0
2
1 2

Test 21

Verdict: ACCEPTED

input
4 1
2 1
2 0
1 3

correct output
2
1
0 2

user output
2
1
0 2

Test 22

Verdict: ACCEPTED

input
4 1
2 0
0 3
1 0

correct output
2
0

user output
2
0

Test 23

Verdict: ACCEPTED

input
4 2
3 0
1 2
2 3

correct output
1
2
0 2

user output
1
2
0 2

Test 24

Verdict: ACCEPTED

input
4 2
1 0
0 3
0 2

correct output
1
2
1 3

user output
1
2
1 2

Test 25

Verdict: ACCEPTED

input
4 3
3 0
3 2
2 1

correct output
0
3
0 1

user output
0
3
0 1

Test 26

Verdict: ACCEPTED

input
4 3
1 0
3 0
2 0

correct output
1
2
1 3

user output
1
2
1 2

Test 27

Verdict: ACCEPTED

input
10 3
3 0
8 1
9 5
0 4
...

correct output
2
3
0 5

user output
2
3
0 5

Test 28

Verdict:

input
100 4
32 66
29 26
86 0
71 83
...

correct output
12
4
86 89

user output
9
0

Test 29

Verdict:

input
1000 1
155 994
213 449
582 440
277 0
...

correct output
22
1
1 330

user output
13
0

Test 30

Verdict:

input
2500 10
517 660
971 230
982 1721
2200 2124
...

correct output
23
4
294 943

user output
14
0

Test 31

Verdict:

input
5000 1
1611 2785
2978 4796
3783 4548
1074 1256
...

correct output
34
1
0 1611

user output
19
0

Test 32

Verdict:

input
5000 2
3110 2737
2365 2830
2914 874
3720 2637
...

correct output
30
2
844 1623

user output
18
0

Test 33

Verdict:

input
5000 4
664 4317
295 764
4857 1869
1111 1915
...

correct output
33
4
541 2936

user output
20
1
1036 2674

Test 34

Verdict:

input
5000 8
4033 4112
3295 1781
1623 933
2035 1665
...

correct output
30
7
2605 4351

user output
20
0

Test 35

Verdict:

input
5000 20
2304 353
834 2090
1767 72
3026 4211
...

correct output
26
12
1708 3762

user output
19
5
1484 745

Test 36

Verdict:

input
5000 100
1688 3447
496 2607
1054 2586
4259 2671
...

correct output
29
5
1379 2879

user output
18
0

Test 37

Verdict:

input
5000 1000
638 3198
3452 4568
2723 2277
1947 4539
...

correct output
28
6
517 4411

user output
17
1
4907 3844

Test 38

Verdict:

input
5000 2000
1451 4112
1730 1026
1556 1248
4723 678
...

correct output
28
6
82 4161

user output
17
0

Test 39

Verdict:

input
5000 4000
3618 1301
2744 1363
1705 3118
2385 2886
...

correct output
28
11
1526 2510

user output
21
0

Test 40

Verdict:

input
5000 4999
1647 992
3574 4278
2808 2380
3945 287
...

correct output
25
10
510 839

user output
19
0

Test 41

Verdict:

input
100 4
48 94
54 34
25 31
12 16
...

correct output
18
3
13 24

user output
15
0

Test 42

Verdict:

input
1000 1
649 341
964 65
43 702
226 543
...

correct output
54
1
23 833

user output
30
0

Test 43

Verdict:

input
2500 10
2238 1206
1470 365
1938 1220
962 2009
...

correct output
51
10
333 1068

user output
32
0

Test 44

Verdict:

input
5000 1
1600 4821
4466 2988
261 1010
1777 2935
...

correct output
84
1
36 723

user output
44
0

Test 45

Verdict:

input
5000 2
2161 2849
1729 1347
1763 2560
2098 2899
...

correct output
112
2
1 1769

user output
58
0

Test 46

Verdict:

input
5000 4
3961 4831
2920 3199
4703 3118
201 1241
...

correct output
112
4
43 4157

user output
59
0

Test 47

Verdict:

input
5000 8
3226 1183
3536 3297
2501 261
3071 4107
...

correct output
122
8
133 2017

user output
67
0

Test 48

Verdict:

input
5000 20
1221 3603
3259 3147
3676 1561
4574 962
...

correct output
86
20
128 2391

user output
55
0

Test 49

Verdict:

input
5000 100
50 2333
699 2904
4502 392
2177 3778
...

correct output
75
42
1627 3129

user output
60
1
3659 4620

Test 50

Verdict:

input
5000 1000
1025 4349
3214 4639
4004 2506
652 4796
...

correct output
38
10
2964 4732

user output
24
0

Test 51

Verdict:

input
5000 2000
4108 791
4770 1666
4203 4197
2566 728
...

correct output
48
19
2640 4559

user output
33
0

Test 52

Verdict:

input
5000 4000
2183 3550
857 549
4752 3563
4198 4895
...

correct output
69
26
3244 4780

user output
46
0

Test 53

Verdict:

input
5000 4999
4282 2328
4163 653
929 3214
3631 4207
...

correct output
79
26
2794 4878

user output
52
0

Test 54

Verdict:

input
100 4
51 84
32 89
92 51
67 4
...

correct output
5
3
14 50

user output
5
0

Test 55

Verdict:

input
1000 1
942 999
402 534
533 278
228 908
...

correct output
10
1
0 968

user output
7
0

Test 56

Verdict:

input
2500 10
1639 991
640 223
1940 1067
801 257
...

correct output
12
2
2075 2395

user output
8
0

Test 57

Verdict:

input
5000 1
1585 3293
3686 3851
1447 1604
392 2681
...

correct output
14
0

user output
8
0

Test 58

Verdict:

input
5000 2
626 3760
2593 3177
1343 889
1377 596
...

correct output
14
0

user output
8
0

Test 59

Verdict:

input
5000 4
1462 182
3060 4479
3021 4111
3145 2887
...

correct output
12
2
2219 3145

user output
8
0

Test 60

Verdict:

input
5000 8
671 2837
3952 4186
828 1632
3885 2545
...

correct output
10
1
0 2405

user output
7
0

Test 61

Verdict:

input
5000 20
3274 1781
3151 566
1298 1210
495 4010
...

correct output
14
0

user output
8
0

Test 62

Verdict:

input
5000 100
487 1275
4234 2960
1502 3713
2471 819
...

correct output
10
1
0 4411

user output
7
0

Test 63

Verdict:

input
5000 1000
2192 4468
4475 4665
81 4277
998 1960
...

correct output
12
1
0 910

user output
8
0

Test 64

Verdict:

input
5000 2000
686 0
3311 3404
176 2362
119 2765
...

correct output
14
1
0 3007

user output
9
0

Test 65

Verdict:

input
5000 4000
2848 3939
1514 2396
527 821
2586 4938
...

correct output
16
3
318 3675

user output
11
0

Test 66

Verdict:

input
5000 4999
2128 1367
1616 1575
4936 3022
339 4210
...

correct output
10
0

user output
6
0

Test 67

Verdict: ACCEPTED

input
5000 4999
2858 558
4677 2444
3042 610
1950 4352
...

correct output
0
4999
0 1971

user output
0
4999
0 1971

Test 68

Verdict: ACCEPTED

input
5000 4999
0 3957
0 2864
0 2018
2678 0
...

correct output
2
0

user output
2
0

Test 69

Verdict: ACCEPTED

input
5000 1
2654 1880
2560 3683
4613 596
4860 1233
...

correct output
4998
1
0 1782

user output
4998
1
0 1782

Test 70

Verdict: ACCEPTED

input
5000 1
3762 0
0 2803
0 1387
610 0
...

correct output
2
0

user output
2
0

Test 71

Verdict: ACCEPTED

input
10 4
3 0
8 4
5 7
3 8
...

correct output
3
4
3 5

user output
3
4
3 5

Test 72

Verdict: ACCEPTED

input
10 5
1 3
5 9
9 2
6 3
...

correct output
2
5
2 6

user output
2
5
2 6