CSES - IZhO 2017, day 2 - Results
Submission details
Task:Hard route
Sender:ollpu
Submission time:2019-02-10 16:55:10 +0200
Language:C++
Status:READY
Result:52
Feedback
groupverdictscore
#1ACCEPTED19
#2ACCEPTED33
#30
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1, 2, 3details
#2ACCEPTED0.04 s1, 2, 3details
#3ACCEPTED0.04 s1, 2, 3details
#4ACCEPTED0.03 s1, 2, 3details
#5ACCEPTED0.04 s1, 2, 3details
#6ACCEPTED0.04 s1, 2, 3details
#7ACCEPTED0.04 s1, 2, 3details
#8ACCEPTED0.04 s1, 2, 3details
#9ACCEPTED0.05 s1, 2, 3details
#10ACCEPTED0.04 s1, 2, 3details
#11ACCEPTED0.04 s1, 2, 3details
#12ACCEPTED0.04 s1, 2, 3details
#13ACCEPTED0.04 s1, 2, 3details
#14ACCEPTED0.05 s1, 2, 3details
#15ACCEPTED0.04 s1, 2, 3details
#16ACCEPTED0.04 s1, 2, 3details
#17ACCEPTED0.03 s1, 2, 3details
#18ACCEPTED0.03 s1, 2, 3details
#19ACCEPTED0.04 s1, 2, 3details
#20ACCEPTED0.04 s1, 2, 3details
#21ACCEPTED0.04 s1, 2, 3details
#22ACCEPTED0.04 s1, 2, 3details
#23ACCEPTED0.04 s1, 2, 3details
#24ACCEPTED0.04 s1, 2, 3details
#25ACCEPTED0.04 s2, 3details
#26ACCEPTED0.04 s2, 3details
#27ACCEPTED0.04 s2, 3details
#28ACCEPTED0.05 s2, 3details
#29ACCEPTED0.04 s2, 3details
#30ACCEPTED0.04 s2, 3details
#31ACCEPTED0.05 s2, 3details
#32ACCEPTED0.04 s2, 3details
#33ACCEPTED0.05 s2, 3details
#34ACCEPTED0.05 s2, 3details
#35ACCEPTED0.04 s2, 3details
#36ACCEPTED0.04 s2, 3details
#37ACCEPTED0.05 s2, 3details
#38ACCEPTED0.04 s2, 3details
#39ACCEPTED0.04 s2, 3details
#40ACCEPTED0.05 s2, 3details
#41ACCEPTED0.04 s2, 3details
#42ACCEPTED0.04 s2, 3details
#43ACCEPTED0.05 s2, 3details
#44ACCEPTED0.05 s2, 3details
#45ACCEPTED0.04 s2, 3details
#46ACCEPTED0.04 s2, 3details
#47ACCEPTED0.04 s2, 3details
#48ACCEPTED0.05 s2, 3details
#49ACCEPTED0.84 s3details
#50ACCEPTED0.85 s3details
#51ACCEPTED0.85 s3details
#52ACCEPTED0.84 s3details
#53ACCEPTED0.78 s3details
#54ACCEPTED0.81 s3details
#55ACCEPTED0.78 s3details
#56ACCEPTED0.83 s3details
#57ACCEPTED0.84 s3details
#58ACCEPTED0.82 s3details
#59ACCEPTED0.83 s3details
#60ACCEPTED0.82 s3details
#61--3details
#62--3details
#63ACCEPTED1.00 s3details
#64ACCEPTED0.98 s3details
#65ACCEPTED0.97 s3details
#66ACCEPTED0.97 s3details
#67ACCEPTED0.95 s3details
#68ACCEPTED0.96 s3details
#69ACCEPTED0.93 s3details
#70ACCEPTED0.91 s3details
#71ACCEPTED0.89 s3details
#72ACCEPTED0.89 s3details
#73ACCEPTED0.96 s3details
#74ACCEPTED0.87 s3details
#75ACCEPTED0.89 s3details
#76ACCEPTED0.84 s3details
#77ACCEPTED0.73 s3details
#78ACCEPTED0.53 s3details

Code

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
vector<int> v[500000];
vector<pair<int, int>> ov[500000];
long mv = 0, mc = 0;
pair<int, int> h1(int i, int p=-1) {
  ov[i].reserve(v[i].size());
  pair<int, int> trt{0, 1};
  for (int j : v[i]) {
    if (j == p) continue;
    auto cv = h1(j, i);
    ov[i].push_back(cv);
    if (cv.F > trt.F) trt = {cv.F, 0};
    if (cv.F == trt.F) trt.S += cv.S;
  }
  trt.F++;
  return trt;
}
void h2(int i, int p=-1) {
  {
    map<int, int> am;
    auto &chv = ov[i];
    for (auto cv : chv) {
      am[cv.F] += cv.S;
    }
    if (v[i].size() == 1) am[0] = 1;
    int xi = 0;
    for (int j : v[i]) {
      if (j == p) continue;
      am[chv[xi].F] -= chv[xi].S;
      auto it = am.rbegin();
      pair<int, int> gp = *it;
      if (gp.S == 0) {
        it++, gp = *it;
      }
      gp.F++;
      ov[j].push_back(gp);
      am[chv[xi].F] += chv[xi].S;
      xi++;
    }
  }
  for (int j : v[i]) {
    if (j == p) continue;
    h2(j, i);
  }
  if (v[i].size() == 1) return;
  {
    map<int, int> uq, am;
    auto &chv = ov[i];
    for (auto cv : chv) {
      uq[cv.F]++;
      am[cv.F] += cv.S;
    }
    for (auto cv : chv) {
      am[cv.F] -= cv.S;
      if (am[cv.F] == 0) am.erase(cv.F);
      uq[cv.F]--;
      
      int opc = min(2, int(am.size()));
      int ops[2];
      auto it = am.rbegin();
      for (int cc = 0; cc < opc; ++cc, ++it) {
        ops[cc] = it->F;
      }
      for (int cc = 0; cc < opc; ++cc) {
        int co = ops[cc];
        uq[co]--;
        int sup = 0;
        for (int cc2 = 0; cc2 < opc; ++cc2) {
          if (uq[ops[cc2]]) sup = max(sup, ops[cc2]);
        }
        long rv = long(co+cv.F)*sup;
        if (rv > mv) mv = rv, mc = 0;
        if (rv == mv) mc += long(cv.S)*am[co];
        uq[co]++;
      }
      am[cv.F] += cv.S;
      uq[cv.F]++;
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n-1; ++i) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  h1(0);
  h2(0);
  if (mv == 0) mc = 2;
  cout << mv << " " << mc/2 << endl;
}

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: ACCEPTED

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

correct output
77624 1

user output
77624 1

Test 26

Group: 2, 3

Verdict: ACCEPTED

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

correct output
75180 3

user output
75180 3

Test 27

Group: 2, 3

Verdict: ACCEPTED

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

correct output
67689 3

user output
67689 3

Test 28

Group: 2, 3

Verdict: ACCEPTED

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

correct output
75030 3

user output
75030 3

Test 29

Group: 2, 3

Verdict: ACCEPTED

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

correct output
1565001 2

user output
1565001 2

Test 30

Group: 2, 3

Verdict: ACCEPTED

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

correct output
1565001 2

user output
1565001 2

Test 31

Group: 2, 3

Verdict: ACCEPTED

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

correct output
1565001 2

user output
1565001 2

Test 32

Group: 2, 3

Verdict: ACCEPTED

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

correct output
1565001 2

user output
1565001 2

Test 33

Group: 2, 3

Verdict: ACCEPTED

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

correct output
4686874 1

user output
4686874 1

Test 34

Group: 2, 3

Verdict: ACCEPTED

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

correct output
4686874 1

user output
4686874 1

Test 35

Group: 2, 3

Verdict: ACCEPTED

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

correct output
4686874 1

user output
4686874 1

Test 36

Group: 2, 3

Verdict: ACCEPTED

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

correct output
4686874 1

user output
4686874 1

Test 37

Group: 2, 3

Verdict: ACCEPTED

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

correct output
0 1

user output
0 1

Test 38

Group: 2, 3

Verdict: ACCEPTED

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

correct output
0 1

user output
0 1

Test 39

Group: 2, 3

Verdict: ACCEPTED

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

correct output
1996002 10

user output
1996002 10

Test 40

Group: 2, 3

Verdict: ACCEPTED

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

correct output
498002 45

user output
498002 45

Test 41

Group: 2, 3

Verdict: ACCEPTED

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

correct output
124002 190

user output
124002 190

Test 42

Group: 2, 3

Verdict: ACCEPTED

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

correct output
19602 1225

user output
19602 1225

Test 43

Group: 2, 3

Verdict: ACCEPTED

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

correct output
4802 4950

user output
4802 4950

Test 44

Group: 2, 3

Verdict: ACCEPTED

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

correct output
1152 19900

user output
1152 19900

Test 45

Group: 2, 3

Verdict: ACCEPTED

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

correct output
162 124750

user output
162 124750

Test 46

Group: 2, 3

Verdict: ACCEPTED

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

correct output
32 499500

user output
32 499500

Test 47

Group: 2, 3

Verdict: ACCEPTED

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

correct output
8 2878800

user output
8 2878800

Test 48

Group: 2, 3

Verdict: ACCEPTED

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

correct output
2 12492501

user output
2 12492501

Test 49

Group: 3

Verdict: ACCEPTED

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

correct output
13000624 8

user output
13000624 8

Test 50

Group: 3

Verdict: ACCEPTED

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

correct output
14000392 7

user output
14000392 7

Test 51

Group: 3

Verdict: ACCEPTED

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

correct output
13250477 3

user output
13250477 3

Test 52

Group: 3

Verdict: ACCEPTED

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

correct output
13000260 8

user output
13000260 8

Test 53

Group: 3

Verdict: ACCEPTED

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

correct output
15625250001 2

user output
15625250001 2

Test 54

Group: 3

Verdict: ACCEPTED

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

correct output
15625250001 2

user output
15625250001 2

Test 55

Group: 3

Verdict: ACCEPTED

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

correct output
15625250001 2

user output
15625250001 2

Test 56

Group: 3

Verdict: ACCEPTED

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

correct output
15625250001 2

user output
15625250001 2

Test 57

Group: 3

Verdict: ACCEPTED

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

correct output
46874937499 1

user output
46874937499 1

Test 58

Group: 3

Verdict: ACCEPTED

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

correct output
46874937499 1

user output
46874937499 1

Test 59

Group: 3

Verdict: ACCEPTED

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

correct output
46874937499 1

user output
46874937499 1

Test 60

Group: 3

Verdict: ACCEPTED

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

correct output
46874937499 1

user output
46874937499 1

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: ACCEPTED

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

correct output
19999600002 10

user output
19999600002 10

Test 64

Group: 3

Verdict: ACCEPTED

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

correct output
4999800002 45

user output
4999800002 45

Test 65

Group: 3

Verdict: ACCEPTED

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

correct output
1249900002 190

user output
1249900002 190

Test 66

Group: 3

Verdict: ACCEPTED

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

correct output
199960002 1225

user output
199960002 1225

Test 67

Group: 3

Verdict: ACCEPTED

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

correct output
49980002 4950

user output
49980002 4950

Test 68

Group: 3

Verdict: ACCEPTED

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

correct output
12490002 19900

user output
12490002 19900

Test 69

Group: 3

Verdict: ACCEPTED

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

correct output
1996002 124750

user output
1996002 124750

Test 70

Group: 3

Verdict: ACCEPTED

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

correct output
498002 499500

user output
498002 499500

Test 71

Group: 3

Verdict: ACCEPTED

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

correct output
124002 1997001

user output
124002 1997001

Test 72

Group: 3

Verdict: ACCEPTED

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

correct output
80000 3121251

user output
80000 3121251

Test 73

Group: 3

Verdict: ACCEPTED

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

correct output
5000 49985001

user output
5000 49985001

Test 74

Group: 3

Verdict: ACCEPTED

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

correct output
1250 199970001

user output
1250 199970001

Test 75

Group: 3

Verdict: ACCEPTED

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

correct output
200 1249925001

user output
200 1249925001

Test 76

Group: 3

Verdict: ACCEPTED

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

correct output
50 4999850001

user output
50 4999850001

Test 77

Group: 3

Verdict: ACCEPTED

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

correct output
8 31249625001

user output
8 31249625001

Test 78

Group: 3

Verdict: ACCEPTED

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

correct output
2 124999250001

user output
2 124999250001