CSES - IZhO 2017, day 2 - Results
Submission details
Task:Hard route
Sender:Olli
Submission time:2019-02-10 18:09:15 +0200
Language:C++
Status:READY
Result:19
Feedback
groupverdictscore
#1ACCEPTED19
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.03 s1, 2, 3details
#8ACCEPTED0.03 s1, 2, 3details
#9ACCEPTED0.03 s1, 2, 3details
#10ACCEPTED0.03 s1, 2, 3details
#11ACCEPTED0.05 s1, 2, 3details
#12ACCEPTED0.05 s1, 2, 3details
#13ACCEPTED0.05 s1, 2, 3details
#14ACCEPTED0.04 s1, 2, 3details
#15ACCEPTED0.02 s1, 2, 3details
#16ACCEPTED0.01 s1, 2, 3details
#17ACCEPTED0.02 s1, 2, 3details
#18ACCEPTED0.01 s1, 2, 3details
#19ACCEPTED0.01 s1, 2, 3details
#20ACCEPTED0.02 s1, 2, 3details
#21ACCEPTED0.01 s1, 2, 3details
#22ACCEPTED0.01 s1, 2, 3details
#23ACCEPTED0.03 s1, 2, 3details
#24ACCEPTED0.06 s1, 2, 3details
#250.03 s2, 3details
#260.01 s2, 3details
#270.01 s2, 3details
#280.02 s2, 3details
#290.02 s2, 3details
#300.02 s2, 3details
#310.02 s2, 3details
#320.02 s2, 3details
#330.01 s2, 3details
#340.01 s2, 3details
#350.02 s2, 3details
#360.02 s2, 3details
#370.01 s2, 3details
#380.02 s2, 3details
#390.01 s2, 3details
#400.02 s2, 3details
#410.02 s2, 3details
#420.01 s2, 3details
#430.02 s2, 3details
#440.02 s2, 3details
#450.01 s2, 3details
#460.03 s2, 3details
#470.02 s2, 3details
#480.02 s2, 3details
#490.03 s3details
#500.01 s3details
#510.02 s3details
#520.02 s3details
#530.01 s3details
#540.02 s3details
#550.02 s3details
#560.02 s3details
#570.01 s3details
#580.03 s3details
#590.02 s3details
#600.02 s3details
#610.02 s3details
#620.02 s3details
#630.02 s3details
#640.03 s3details
#650.01 s3details
#660.01 s3details
#670.02 s3details
#680.03 s3details
#690.02 s3details
#700.02 s3details
#710.03 s3details
#720.02 s3details
#730.01 s3details
#740.02 s3details
#750.01 s3details
#760.02 s3details
#770.02 s3details
#780.02 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < g[a].size(); ++j) {
                  ~~^~~~~~~~~~~~~
input/code.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < rou.size(); ++j) {
                    ~~^~~~~~~~~~~~

Code

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int N = 111;

int d[N][N];
int p[N];
int f[10][N];
int de[N];

vector<int> g[N];
bool s[N];
int lca(int a, int b) {
	if(de[a] > de[b]) {
		swap(a, b);
	}
	for(int bi = 9; bi >= 0; --bi) {
		int neD = de[b] - (1<<bi);
		if(neD < de[a]) continue;
		b = f[bi][b];
	}
	if(a == b) return a;
	for(int bi = 9; bi >= 0; --bi) {
		if(f[bi][a] == f[bi][b]) continue;
		a = f[bi][a];
		b = f[bi][b];
	}
	return p[a];
}

int main() {
	int n;
	cin >> n;
	for(int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	queue<int> q;
	q.push(1);
	while(!q.empty()) {
		int a = q.front();
		q.pop();
		s[a] = true;
		for(int j = 0; j < g[a].size(); ++j) {
			int b = g[a][j];
			if(s[b]) continue;
			p[b] = a;
			f[0][b] = a;
			de[b] = de[a] + 1;
			q.push(b);
		}
	}

	f[0][1] = 1;

	for(int i = 1; i < 10; ++i) {
		for(int j = 1; j <= n; ++j) {
			f[i][j] = f[i-1][f[i-1][j]];
		}
	}

	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			d[i][j] = de[i] + de[j] - 2*de[lca(i, j)];
		}
	}

	int ma = 0;
	int am = 0;
	for(int a = 1; a <= n; ++a) {
		if(g[a].size() > 1) continue;
		for(int b = a+1; b <= n; ++b) {
			if(g[b].size() > 1) continue;
			int H = 0;
			int c = lca(a, b);
			vector<int> rou;
			for(int i = 1; i <= n; ++i) {
				if(lca(c, i) != c) continue;
				if(lca(a, i) == i) {
					rou.push_back(i);
				} else if (lca(b, i) == i) {
					rou.push_back(i);
				}
			}
			for(int i = 1; i <= n; ++i) {
				int mi = 1e9;
				for(int j = 0; j < rou.size(); ++j) {
					mi = min(mi, d[i][rou[j]]);
				}
				H = max(mi, H);
			}

			if(H*d[a][b] == ma) {
				++am;
			} else if (H*d[a][b] > ma) {
				ma = H*d[a][b];
				am = 1;
			}
		}
	}

	cout << ma << " " << am << "\n";

}

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)