CSES - Siperia opettaa 3.0

CSES - Siperia opettaa 3.0 - Results

Submission details
Task:	Toll Roads
Sender:	zxc
Submission time:	2016-07-29 16:51:43 +0300
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	100

Test results
test	verdict	time
#1	ACCEPTED	0.06 s	details
#2	ACCEPTED	0.05 s	details
#3	ACCEPTED	0.05 s	details
#4	ACCEPTED	0.05 s	details
#5	ACCEPTED	0.06 s	details
#6	ACCEPTED	0.06 s	details
#7	ACCEPTED	0.06 s	details
#8	ACCEPTED	0.05 s	details
#9	ACCEPTED	0.05 s	details
#10	ACCEPTED	0.06 s	details
#11	ACCEPTED	0.05 s	details
#12	ACCEPTED	0.05 s	details
#13	ACCEPTED	0.05 s	details
#14	ACCEPTED	0.06 s	details
#15	ACCEPTED	0.06 s	details
#16	ACCEPTED	0.05 s	details
#17	ACCEPTED	0.05 s	details
#18	ACCEPTED	0.06 s	details
#19	ACCEPTED	0.05 s	details
#20	ACCEPTED	0.05 s	details
#21	ACCEPTED	0.05 s	details
#22	ACCEPTED	0.06 s	details
#23	ACCEPTED	0.06 s	details
#24	ACCEPTED	0.06 s	details
#25	ACCEPTED	0.06 s	details
#26	ACCEPTED	0.05 s	details
#27	ACCEPTED	0.05 s	details
#28	ACCEPTED	0.02 s	details
#29	ACCEPTED	0.06 s	details
#30	ACCEPTED	0.29 s	details
#31	ACCEPTED	0.77 s	details
#32	ACCEPTED	0.78 s	details
#33	ACCEPTED	0.80 s	details
#34	ACCEPTED	0.88 s	details
#35	ACCEPTED	1.82 s	details
#36	ACCEPTED	1.93 s	details
#37	ACCEPTED	1.94 s	details
#38	ACCEPTED	1.94 s	details
#39	ACCEPTED	1.94 s	details
#40	ACCEPTED	1.93 s	details
#41	ACCEPTED	0.05 s	details
#42	ACCEPTED	0.07 s	details
#43	ACCEPTED	0.20 s	details
#44	ACCEPTED	0.84 s	details
#45	ACCEPTED	0.83 s	details
#46	ACCEPTED	0.83 s	details
#47	ACCEPTED	0.81 s	details
#48	ACCEPTED	0.90 s	details
#49	ACCEPTED	2.11 s	details
#50	ACCEPTED	1.98 s	details
#51	ACCEPTED	2.00 s	details
#52	ACCEPTED	2.07 s	details
#53	ACCEPTED	2.07 s	details
#54	ACCEPTED	0.05 s	details
#55	ACCEPTED	0.07 s	details
#56	ACCEPTED	0.35 s	details
#57	ACCEPTED	0.60 s	details
#58	ACCEPTED	0.61 s	details
#59	ACCEPTED	0.67 s	details
#60	ACCEPTED	1.36 s	details
#61	ACCEPTED	1.57 s	details
#62	ACCEPTED	1.31 s	details
#63	ACCEPTED	1.47 s	details
#64	ACCEPTED	1.57 s	details
#65	ACCEPTED	1.71 s	details
#66	ACCEPTED	1.33 s	details
#67	ACCEPTED	2.18 s	details
#68	ACCEPTED	0.84 s	details
#69	ACCEPTED	1.01 s	details
#70	ACCEPTED	0.56 s	details
#71	ACCEPTED	0.05 s	details
#72	ACCEPTED	0.06 s	details

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);
	    ha[x] = max(ha[y], ha[x]);
	    if(pisin[y]+1 > q) {
		w = q;
		q = pisin[y]+1;
	    }
	    else if(pisin[y]+1 > w) {
		w = pisin[y]+1;
	    }
	}
    }
    ha[x] = max(ha[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 = 0;
    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;
	    }
	}
    }
    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 = qwe;
	    if(pisin[y]+1 == p1) {
		nqwe = max(nqwe, p2+p3);
	    }
	    else if(pisin[y]+1 == p2) {
		nqwe = max(nqwe, p1+p3);
	    }
	    else {
		nqwe = max(nqwe, 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<<i<<' '<<best.S.F<<'\n';
    }
    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 ...` view save

correct output
`2 3 2 6` view save

user output
`2 3 2 6` view save

Test 2

Verdict: ACCEPTED

input
`5 2 0 1 0 2 0 3 0 4` view save

correct output
`2 0` view save

user output
`2 0` view save

Test 3

Verdict: ACCEPTED

input
`2 1 0 1` view save

correct output
`0 1 0 1` view save

user output
`0 1 0 1` view save

Test 4

Verdict: ACCEPTED

input
`3 1 0 1 2 1` view save

correct output
`1 1 0 1` view save

user output
`1 1 0 1` view save

Test 5

Verdict: ACCEPTED

input
`3 1 0 2 1 2` view save

correct output
`1 1 0 2` view save

user output
`1 1 0 2` view save

Test 6

Verdict: ACCEPTED

input
`3 2 0 2 1 2` view save

correct output
`0 2 0 1` view save

user output
`0 2 0 1` view save

Test 7

Verdict: ACCEPTED

input
`4 1 0 3 0 1 3 2` view save

correct output
`2 1 0 3` view save

user output
`2 1 0 1` view save

Test 8

Verdict: ACCEPTED

input
`4 2 0 3 0 1 3 2` view save

correct output
`1 2 0 2` view save

user output
`1 2 0 2` view save

Test 9

Verdict: ACCEPTED

input
`4 3 0 3 0 1 3 2` view save

correct output
`0 3 1 2` view save

user output
`0 3 1 2` view save

Test 10

Verdict: ACCEPTED

input
`4 1 0 1 0 2 0 3` view save

correct output
`2 0` view save

user output
`2 0` view save

Test 11

Verdict: ACCEPTED

input
`4 2 0 1 0 2 0 3` view save

correct output
`1 2 1 2` view save

user output
`1 2 1 2` view save

Test 12

Verdict: ACCEPTED

input
`4 3 0 1 0 2 0 3` view save

correct output
`1 2 1 2` view save

user output
`1 2 1 2` view save

Test 13

Verdict: ACCEPTED

input
`6 3 0 1 0 2 0 3 2 4 ...` view save

correct output
`2 2 2 3` view save

user output
`2 2 2 3` view save

Test 14

Verdict: ACCEPTED

input
`6 3 0 1 0 2 0 3 2 4 ...` view save

correct output
`2 1 0 2` view save

user output
`2 1 0 2` view save

Test 15

Verdict: ACCEPTED

input
`8 5 0 1 1 2 2 3 0 4 ...` view save

correct output
`2 4 2 5` view save

user output
`2 4 2 5` view save

Test 16

Verdict: ACCEPTED

input
`2 1 0 1` view save

correct output
`0 1 0 1` view save

user output
`0 1 0 1` view save

Test 17

Verdict: ACCEPTED

input
`3 1 2 1 0 2` view save

correct output
`1 1 0 2` view save

user output
`1 1 0 2` view save

Test 18

Verdict: ACCEPTED

input
`3 1 0 2 0 1` view save

correct output
`1 1 0 2` view save

user output
`1 1 0 1` view save

Test 19

Verdict: ACCEPTED

input
`3 2 1 0 1 2` view save

correct output
`0 2 0 2` view save

user output
`0 2 0 2` view save

Test 20

Verdict: ACCEPTED

input
`3 2 0 1 0 2` view save

correct output
`0 2 1 2` view save

user output
`0 2 1 2` view save

Test 21

Verdict: ACCEPTED

input
`4 1 2 1 2 0 1 3` view save

correct output
`2 1 0 2` view save

user output
`2 1 0 2` view save

Test 22

Verdict: ACCEPTED

input
`4 1 2 0 0 3 1 0` view save

correct output
`2 0` view save

user output
`2 0` view save

Test 23

Verdict: ACCEPTED

input
`4 2 3 0 1 2 2 3` view save

correct output
`1 2 0 2` view save

user output
`1 2 0 2` view save

Test 24

Verdict: ACCEPTED

input
`4 2 1 0 0 3 0 2` view save

correct output
`1 2 1 3` view save

user output
`1 2 1 2` view save

Test 25

Verdict: ACCEPTED

input
`4 3 3 0 3 2 2 1` view save

correct output
`0 3 0 1` view save

user output
`0 3 0 1` view save

Test 26

Verdict: ACCEPTED

input
`4 3 1 0 3 0 2 0` view save

correct output
`1 2 1 3` view save

user output
`1 2 1 2` view save

Test 27

Verdict: ACCEPTED

input
`10 3 3 0 8 1 9 5 0 4 ...` view save

correct output
`2 3 0 5` view save

user output
`2 3 0 5` view save

Test 28

Verdict: ACCEPTED

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

correct output
`12 4 86 89` view save

user output
`12 4 86 89` view save

Test 29

Verdict: ACCEPTED

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

correct output
`22 1 1 330` view save

user output
`22 1 1 330` view save

Test 30

Verdict: ACCEPTED

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

correct output
`23 4 294 943` view save

user output
`23 4 294 943` view save

Test 31

Verdict: ACCEPTED

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

correct output
`34 1 0 1611` view save

user output
`34 1 0 1611` view save

Test 32

Verdict: ACCEPTED

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

correct output
`30 2 844 1623` view save

user output
`30 2 844 1623` view save

Test 33

Verdict: ACCEPTED

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

correct output
`33 4 541 2936` view save

user output
`33 4 541 2936` view save

Test 34

Verdict: ACCEPTED

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

correct output
`30 7 2605 4351` view save

user output
`30 7 2605 4351` view save

Test 35

Verdict: ACCEPTED

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

correct output
`26 12 1708 3762` view save

user output
`26 12 1708 3762` view save

Test 36

Verdict: ACCEPTED

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

correct output
`29 5 1379 2879` view save

user output
`29 5 1379 2879` view save

Test 37

Verdict: ACCEPTED

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

correct output
`28 6 517 4411` view save

user output
`28 6 517 4411` view save

Test 38

Verdict: ACCEPTED

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

correct output
`28 6 82 4161` view save

user output
`28 6 82 4161` view save

Test 39

Verdict: ACCEPTED

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

correct output
`28 11 1526 2510` view save

user output
`28 11 1526 2510` view save

Test 40

Verdict: ACCEPTED

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

correct output
`25 10 510 839` view save

user output
`25 10 510 839` view save

Test 41

Verdict: ACCEPTED

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

correct output
`18 3 13 24` view save

user output
`18 3 13 24` view save

Test 42

Verdict: ACCEPTED

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

correct output
`54 1 23 833` view save

user output
`54 1 23 220` view save

Test 43

Verdict: ACCEPTED

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

correct output
`51 10 333 1068` view save

user output
`51 10 333 1068` view save

Test 44

Verdict: ACCEPTED

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

correct output
`84 1 36 723` view save

user output
`84 1 36 723` view save

Test 45

Verdict: ACCEPTED

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

correct output
`112 2 1 1769` view save

user output
`112 2 1 899` view save

Test 46

Verdict: ACCEPTED

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

correct output
`112 4 43 4157` view save

user output
`112 4 43 3823` view save

Test 47

Verdict: ACCEPTED

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

correct output
`122 8 133 2017` view save

user output
`122 8 133 2017` view save

Test 48

Verdict: ACCEPTED

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

correct output
`86 20 128 2391` view save

user output
`86 20 128 2391` view save

Test 49

Verdict: ACCEPTED

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

correct output
`75 42 1627 3129` view save

user output
`75 42 1627 3129` view save

Test 50

Verdict: ACCEPTED

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

correct output
`38 10 2964 4732` view save

user output
`38 10 2964 4732` view save

Test 51

Verdict: ACCEPTED

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

correct output
`48 19 2640 4559` view save

user output
`48 19 2640 4559` view save

Test 52

Verdict: ACCEPTED

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

correct output
`69 26 3244 4780` view save

user output
`69 26 3244 4780` view save

Test 53

Verdict: ACCEPTED

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

correct output
`79 26 2794 4878` view save

user output
`79 26 2794 4878` view save

Test 54

Verdict: ACCEPTED

input
`100 4 51 84 32 89 92 51 67 4 ...` view save

correct output
`5 3 14 50` view save

user output
`5 3 14 50` view save

Test 55

Verdict: ACCEPTED

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

correct output
`10 1 0 968` view save

user output
`10 1 0 968` view save

Test 56

Verdict: ACCEPTED

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

correct output
`12 2 2075 2395` view save

user output
`12 2 2075 2395` view save

Test 57

Verdict: ACCEPTED

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

correct output
`14 0` view save

user output
`14 0` view save

Test 58

Verdict: ACCEPTED

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

correct output
`14 0` view save

user output
`14 0` view save

Test 59

Verdict: ACCEPTED

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

correct output
`12 2 2219 3145` view save

user output
`12 2 2219 3145` view save

Test 60

Verdict: ACCEPTED

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

correct output
`10 1 0 2405` view save

user output
`10 1 0 2405` view save

Test 61

Verdict: ACCEPTED

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

correct output
`14 0` view save

user output
`14 0` view save

Test 62

Verdict: ACCEPTED

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

correct output
`10 1 0 4411` view save

user output
`10 1 0 4411` view save

Test 63

Verdict: ACCEPTED

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

correct output
`12 1 0 910` view save

user output
`12 1 0 910` view save

Test 64

Verdict: ACCEPTED

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

correct output
`14 1 0 3007` view save

user output
`14 1 0 3007` view save

Test 65

Verdict: ACCEPTED

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

correct output
`16 3 318 3675` view save

user output
`16 3 318 3675` view save

Test 66

Verdict: ACCEPTED

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

correct output
`10 0` view save

user output
`10 0` view save

Test 67

Verdict: ACCEPTED

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

correct output
`0 4999 0 1971` view save

user output
`0 4999 0 1971` view save

Test 68

Verdict: ACCEPTED

input
`5000 4999 0 3957 0 2864 0 2018 2678 0 ...` view save

correct output
`2 0` view save

user output
`2 0` view save

Test 69

Verdict: ACCEPTED

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

correct output
`4998 1 0 1782` view save

user output
`4998 1 0 1782` view save

Test 70

Verdict: ACCEPTED

input
`5000 1 3762 0 0 2803 0 1387 610 0 ...` view save

correct output
`2 0` view save

user output
`2 0` view save

Test 71

Verdict: ACCEPTED

input
`10 4 3 0 8 4 5 7 3 8 ...` view save

correct output
`3 4 3 5` view save

user output
`3 4 3 5` view save

Test 72

Verdict: ACCEPTED

input
`10 5 1 3 5 9 9 2 6 3 ...` view save

correct output
`2 5 2 6` view save

user output
`2 5 2 6` view save

Siperia opettaa 3.0

Toll Roads

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Test 62

Test 63

Test 64

Test 65

Test 66

Test 67

Test 68

Test 69

Test 70

Test 71

Test 72

Tasks

Submissions (zxc)