CSES - IZhO 2017, day 2 - Results
Submission details
Task:Hard route
Sender:ollpu
Submission time:2019-02-10 16:50:41 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.21 s1, 2, 3details
#20.04 s1, 2, 3details
#3ACCEPTED0.04 s1, 2, 3details
#4ACCEPTED0.04 s1, 2, 3details
#5ACCEPTED0.04 s1, 2, 3details
#6ACCEPTED0.04 s1, 2, 3details
#70.26 s1, 2, 3details
#80.28 s1, 2, 3details
#90.34 s1, 2, 3details
#100.05 s1, 2, 3details
#110.05 s1, 2, 3details
#12--1, 2, 3details
#130.04 s1, 2, 3details
#140.05 s1, 2, 3details
#150.22 s1, 2, 3details
#160.22 s1, 2, 3details
#170.21 s1, 2, 3details
#180.21 s1, 2, 3details
#190.22 s1, 2, 3details
#200.22 s1, 2, 3details
#210.05 s1, 2, 3details
#220.21 s1, 2, 3details
#230.04 s1, 2, 3details
#240.05 s1, 2, 3details
#250.34 s2, 3details
#260.48 s2, 3details
#270.04 s2, 3details
#280.33 s2, 3details
#29--2, 3details
#30--2, 3details
#31--2, 3details
#32--2, 3details
#330.21 s2, 3details
#340.21 s2, 3details
#350.21 s2, 3details
#360.21 s2, 3details
#370.21 s2, 3details
#380.22 s2, 3details
#390.21 s2, 3details
#400.22 s2, 3details
#410.22 s2, 3details
#420.21 s2, 3details
#430.23 s2, 3details
#440.22 s2, 3details
#450.21 s2, 3details
#460.81 s2, 3details
#470.70 s2, 3details
#480.05 s2, 3details
#490.77 s3details
#500.82 s3details
#510.84 s3details
#520.76 s3details
#530.43 s3details
#540.44 s3details
#550.43 s3details
#560.44 s3details
#570.53 s3details
#580.51 s3details
#590.54 s3details
#600.52 s3details
#610.63 s3details
#620.64 s3details
#630.64 s3details
#640.64 s3details
#650.64 s3details
#660.62 s3details
#670.64 s3details
#680.61 s3details
#690.61 s3details
#700.60 s3details
#710.59 s3details
#720.61 s3details
#730.59 s3details
#740.58 s3details
#75--3details
#760.56 s3details
#770.47 s3details
#780.39 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++;
    }
    if (v[i].size() == 1) return;
  }
  for (int j : v[i]) {
    h2(j, i);
  }
  {
    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:

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

correct output
6 2

user output
(empty)

Test 2

Group: 1, 2, 3

Verdict:

input
4
1 2
2 3
2 4

correct output
2 3

user output
0 1

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:

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

correct output
510 9

user output
(empty)

Test 8

Group: 1, 2, 3

Verdict:

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

correct output
624 1

user output
(empty)

Test 9

Group: 1, 2, 3

Verdict:

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

correct output
624 2

user output
(empty)

Test 10

Group: 1, 2, 3

Verdict:

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

correct output
510 5

user output
0 1

Test 11

Group: 1, 2, 3

Verdict:

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

correct output
676 2

user output
0 1

Test 12

Group: 1, 2, 3

Verdict:

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

correct output
676 2

user output
(empty)

Test 13

Group: 1, 2, 3

Verdict:

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

correct output
676 2

user output
0 1

Test 14

Group: 1, 2, 3

Verdict:

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

correct output
676 2

user output
0 1

Test 15

Group: 1, 2, 3

Verdict:

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

correct output
1836 1

user output
(empty)

Test 16

Group: 1, 2, 3

Verdict:

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

correct output
1836 1

user output
(empty)

Test 17

Group: 1, 2, 3

Verdict:

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

correct output
1836 1

user output
(empty)

Test 18

Group: 1, 2, 3

Verdict:

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

correct output
1836 1

user output
(empty)

Test 19

Group: 1, 2, 3

Verdict:

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

correct output
0 1

user output
(empty)

Test 20

Group: 1, 2, 3

Verdict:

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

correct output
0 1

user output
(empty)

Test 21

Group: 1, 2, 3

Verdict:

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

correct output
1152 6

user output
0 1

Test 22

Group: 1, 2, 3

Verdict:

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

correct output
722 10

user output
(empty)

Test 23

Group: 1, 2, 3

Verdict:

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

correct output
98 78

user output
0 1

Test 24

Group: 1, 2, 3

Verdict:

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

correct output
2 4851

user output
0 1

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
0 1

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
0 1

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
0 1

Test 54

Group: 3

Verdict:

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

correct output
15625250001 2

user output
0 1

Test 55

Group: 3

Verdict:

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

correct output
15625250001 2

user output
0 1

Test 56

Group: 3

Verdict:

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

correct output
15625250001 2

user output
0 1

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
0 1

Test 78

Group: 3

Verdict:

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

correct output
2 124999250001

user output
0 1