CSES - IZhO 2017, day 2

Submission details
Task:	Hard route
Sender:	ollpu
Submission time:	2019-02-10 14:36:56 +0200
Language:	C++
Status:	READY
Result:	52

Feedback
group	verdict	score
#1	ACCEPTED	19
#2	ACCEPTED	33
#3	RUNTIME ERROR	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.03 s	1, 2, 3	details
#2	ACCEPTED	0.03 s	1, 2, 3	details
#3	ACCEPTED	0.04 s	1, 2, 3	details
#4	ACCEPTED	0.04 s	1, 2, 3	details
#5	ACCEPTED	0.04 s	1, 2, 3	details
#6	ACCEPTED	0.04 s	1, 2, 3	details
#7	ACCEPTED	0.04 s	1, 2, 3	details
#8	ACCEPTED	0.04 s	1, 2, 3	details
#9	ACCEPTED	0.05 s	1, 2, 3	details
#10	ACCEPTED	0.04 s	1, 2, 3	details
#11	ACCEPTED	0.04 s	1, 2, 3	details
#12	ACCEPTED	0.04 s	1, 2, 3	details
#13	ACCEPTED	0.05 s	1, 2, 3	details
#14	ACCEPTED	0.05 s	1, 2, 3	details
#15	ACCEPTED	0.04 s	1, 2, 3	details
#16	ACCEPTED	0.03 s	1, 2, 3	details
#17	ACCEPTED	0.04 s	1, 2, 3	details
#18	ACCEPTED	0.04 s	1, 2, 3	details
#19	ACCEPTED	0.04 s	1, 2, 3	details
#20	ACCEPTED	0.05 s	1, 2, 3	details
#21	ACCEPTED	0.03 s	1, 2, 3	details
#22	ACCEPTED	0.03 s	1, 2, 3	details
#23	ACCEPTED	0.05 s	1, 2, 3	details
#24	ACCEPTED	0.04 s	1, 2, 3	details
#25	ACCEPTED	0.05 s	2, 3	details
#26	ACCEPTED	0.05 s	2, 3	details
#27	ACCEPTED	0.04 s	2, 3	details
#28	ACCEPTED	0.05 s	2, 3	details
#29	ACCEPTED	0.05 s	2, 3	details
#30	ACCEPTED	0.06 s	2, 3	details
#31	ACCEPTED	0.05 s	2, 3	details
#32	ACCEPTED	0.04 s	2, 3	details
#33	ACCEPTED	0.04 s	2, 3	details
#34	ACCEPTED	0.05 s	2, 3	details
#35	ACCEPTED	0.04 s	2, 3	details
#36	ACCEPTED	0.04 s	2, 3	details
#37	ACCEPTED	0.06 s	2, 3	details
#38	ACCEPTED	0.04 s	2, 3	details
#39	ACCEPTED	0.05 s	2, 3	details
#40	ACCEPTED	0.04 s	2, 3	details
#41	ACCEPTED	0.05 s	2, 3	details
#42	ACCEPTED	0.05 s	2, 3	details
#43	ACCEPTED	0.05 s	2, 3	details
#44	ACCEPTED	0.04 s	2, 3	details
#45	ACCEPTED	0.06 s	2, 3	details
#46	ACCEPTED	0.04 s	2, 3	details
#47	ACCEPTED	0.04 s	2, 3	details
#48	ACCEPTED	0.04 s	2, 3	details
#49	ACCEPTED	0.87 s	3	details
#50	ACCEPTED	0.88 s	3	details
#51	ACCEPTED	0.89 s	3	details
#52	ACCEPTED	0.89 s	3	details
#53	ACCEPTED	0.84 s	3	details
#54	ACCEPTED	0.86 s	3	details
#55	ACCEPTED	0.82 s	3	details
#56	ACCEPTED	0.83 s	3	details
#57	ACCEPTED	0.87 s	3	details
#58	ACCEPTED	0.87 s	3	details
#59	ACCEPTED	0.85 s	3	details
#60	ACCEPTED	0.85 s	3	details
#61	RUNTIME ERROR	0.78 s	3	details
#62	RUNTIME ERROR	0.83 s	3	details
#63	TIME LIMIT EXCEEDED	--	3	details
#64	TIME LIMIT EXCEEDED	--	3	details
#65	TIME LIMIT EXCEEDED	--	3	details
#66	ACCEPTED	0.98 s	3	details
#67	ACCEPTED	0.97 s	3	details
#68	ACCEPTED	0.98 s	3	details
#69	ACCEPTED	0.95 s	3	details
#70	ACCEPTED	0.95 s	3	details
#71	ACCEPTED	0.89 s	3	details
#72	ACCEPTED	0.89 s	3	details
#73	ACCEPTED	0.96 s	3	details
#74	ACCEPTED	0.87 s	3	details
#75	ACCEPTED	0.87 s	3	details
#76	ACCEPTED	0.84 s	3	details
#77	ACCEPTED	0.72 s	3	details
#78	ACCEPTED	0.54 s	3	details

Code

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
vector<int> v[501010];
vector<pair<int, int>> ov[501010];
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, uq;
  auto &chv = ov[i];
  for (auto cv : chv) {
    am[cv.F] += cv.S;
    uq[cv.F]++;
  }
  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;
    if (am[chv[xi].F] == 0) am.erase(chv[xi].F);
    ov[j].push_back(*am.rbegin());
    ov[j].back().F++;
    am[chv[xi].F] += chv[xi].S;
    h2(j, i);
    xi++;
  }
  if (v[i].size() == 1) return;
  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 ...` view save

correct output
`6 2` view save

user output
`6 2` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
`2 3` view save

user output
`2 3` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
`0 1` view save

user output
`0 1` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`3 2 1 3 1` view save

correct output
`0 1` view save

user output
`0 1` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`3 1 2 2 3` view save

correct output
`0 1` view save

user output
`0 1` view save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2 1 2` view save

correct output
`0 1` view save

user output
`0 1` view save

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 11 34 11 30 30 89 89 61 ...` view save

correct output
`510 9` view save

user output
`510 9` view save

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 84 10 10 46 46 41 84 14 ...` view save

correct output
`624 1` view save

user output
`624 1` view save

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 15 27 15 73 15 49 27 61 ...` view save

correct output
`624 2` view save

user output
`624 2` view save

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 41 49 41 2 49 5 49 87 ...` view save

correct output
`510 5` view save

user output
`510 5` view save

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 60 4 60 99 99 8 99 51 ...` view save

correct output
`676 2` view save

user output
`676 2` view save

Test 12

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 21 54 21 51 51 42 51 46 ...` view save

correct output
`676 2` view save

user output
`676 2` view save

Test 13

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 43 96 43 99 99 100 99 87 ...` view save

correct output
`676 2` view save

user output
`676 2` view save

Test 14

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 89 92 89 61 61 18 61 32 ...` view save

correct output
`676 2` view save

user output
`676 2` view save

Test 15

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 14 46 46 42 42 57 57 71 ...` view save

correct output
`1836 1` view save

user output
`1836 1` view save

Test 16

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 11 15 15 100 100 70 70 92 ...` view save

correct output
`1836 1` view save

user output
`1836 1` view save

Test 17

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 22 66 66 72 72 20 20 80 ...` view save

correct output
`1836 1` view save

user output
`1836 1` view save

Test 18

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 19 70 70 11 11 92 92 14 ...` view save

correct output
`1836 1` view save

user output
`1836 1` view save

Test 19

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 100 42 36 11 20 93 58 27 ...` view save

correct output
`0 1` view save

user output
`0 1` view save

Test 20

Group: 1, 2, 3

Verdict: ACCEPTED

input
`99 71 50 32 52 3 67 54 89 ...` view save

correct output
`0 1` view save

user output
`0 1` view save

Test 21

Group: 1, 2, 3

Verdict: ACCEPTED

input
`97 86 30 35 43 24 46 67 28 ...` view save

correct output
`1152 6` view save

user output
`1152 6` view save

Test 22

Group: 1, 2, 3

Verdict: ACCEPTED

input
`96 9 10 76 49 51 21 49 30 ...` view save

correct output
`722 10` view save

user output
`722 10` view save

Test 23

Group: 1, 2, 3

Verdict: ACCEPTED

input
`92 46 14 70 32 2 73 85 92 ...` view save

correct output
`98 78` view save

user output
`98 78` view save

Test 24

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 84 77 38 77 77 93 77 18 ...` view save

correct output
`2 4851` view save

user output
`2 4851` view save

Test 25

Group: 2, 3

Verdict: ACCEPTED

input
`5000 108 1090 1090 116 108 2557 108 790 ...` view save

correct output
`77624 1` view save

user output
`77624 1` view save

Test 26

Group: 2, 3

Verdict: ACCEPTED

input
`5000 1726 3190 3190 4781 4781 2577 1726 1933 ...` view save

correct output
`75180 3` view save

user output
`75180 3` view save

Test 27

Group: 2, 3

Verdict: ACCEPTED

input
`5000 238 3015 238 3788 3015 763 238 3952 ...` view save

correct output
`67689 3` view save

user output
`67689 3` view save

Test 28

Group: 2, 3

Verdict: ACCEPTED

input
`5000 3811 1893 3811 792 3811 3788 3811 4838 ...` view save

correct output
`75030 3` view save

user output
`75030 3` view save

Test 29

Group: 2, 3

Verdict: ACCEPTED

input
`5000 168 3267 168 4697 4697 4099 4697 4154 ...` view save

correct output
`1565001 2` view save

user output
`1565001 2` view save

Test 30

Group: 2, 3

Verdict: ACCEPTED

input
`5000 3018 2323 3018 1644 1644 3826 1644 4180 ...` view save

correct output
`1565001 2` view save

user output
`1565001 2` view save

Test 31

Group: 2, 3

Verdict: ACCEPTED

input
`5000 1832 3776 1832 4436 4436 1337 4436 567 ...` view save

correct output
`1565001 2` view save

user output
`1565001 2` view save

Test 32

Group: 2, 3

Verdict: ACCEPTED

input
`5000 1991 3088 1991 1990 1990 2727 1990 2434 ...` view save

correct output
`1565001 2` view save

user output
`1565001 2` view save

Test 33

Group: 2, 3

Verdict: ACCEPTED

input
`5000 3243 2207 2207 438 438 2783 2783 2291 ...` view save

correct output
`4686874 1` view save

user output
`4686874 1` view save

Test 34

Group: 2, 3

Verdict: ACCEPTED

input
`5000 4248 2685 2685 175 175 1190 1190 2024 ...` view save

correct output
`4686874 1` view save

user output
`4686874 1` view save

Test 35

Group: 2, 3

Verdict: ACCEPTED

input
`5000 2112 1534 1534 1558 1558 2262 2262 1975 ...` view save

correct output
`4686874 1` view save

user output
`4686874 1` view save

Test 36

Group: 2, 3

Verdict: ACCEPTED

input
`5000 1235 1454 1454 1062 1062 1744 1744 1205 ...` view save

correct output
`4686874 1` view save

user output
`4686874 1` view save

Test 37

Group: 2, 3

Verdict: ACCEPTED

input
`5000 560 803 899 2803 1090 1035 2285 3211 ...` view save

correct output
`0 1` view save

user output
`0 1` view save

Test 38

Group: 2, 3

Verdict: ACCEPTED

input
`4999 1383 1758 1838 1884 2107 2408 3122 4088 ...` view save

correct output
`0 1` view save

user output
`0 1` view save

Test 39

Group: 2, 3

Verdict: ACCEPTED

input
`4996 801 2061 2383 3017 373 355 840 3390 ...` view save

correct output
`1996002 10` view save

user output
`1996002 10` view save

Test 40

Group: 2, 3

Verdict: ACCEPTED

input
`4991 3918 3416 1976 3997 224 3763 3172 1918 ...` view save

correct output
`498002 45` view save

user output
`498002 45` view save

Test 41

Group: 2, 3

Verdict: ACCEPTED

input
`4981 60 2930 1298 4348 1072 4876 4723 4797 ...` view save

correct output
`124002 190` view save

user output
`124002 190` view save

Test 42

Group: 2, 3

Verdict: ACCEPTED

input
`4951 3627 2151 3944 2165 4490 1736 523 2250 ...` view save

correct output
`19602 1225` view save

user output
`19602 1225` view save

Test 43

Group: 2, 3

Verdict: ACCEPTED

input
`4901 1370 139 1739 2587 4146 1261 2596 593 ...` view save

correct output
`4802 4950` view save

user output
`4802 4950` view save

Test 44

Group: 2, 3

Verdict: ACCEPTED

input
`4801 179 2101 3727 3495 1902 2186 1615 2717 ...` view save

correct output
`1152 19900` view save

user output
`1152 19900` view save

Test 45

Group: 2, 3

Verdict: ACCEPTED

input
`4501 2688 2899 1416 818 1286 172 2063 3468 ...` view save

correct output
`162 124750` view save

user output
`162 124750` view save

Test 46

Group: 2, 3

Verdict: ACCEPTED

input
`4001 918 3204 3346 1093 1424 2131 461 988 ...` view save

correct output
`32 499500` view save

user output
`32 499500` view save

Test 47

Group: 2, 3

Verdict: ACCEPTED

input
`4801 3830 1737 2705 4747 3609 1236 4010 3243 ...` view save

correct output
`8 2878800` view save

user output
`8 2878800` view save

Test 48

Group: 2, 3

Verdict: ACCEPTED

input
`5000 1229 3771 3771 722 3625 3771 1466 3771 ...` view save

correct output
`2 12492501` view save

user output
`2 12492501` view save

Test 49

Group: 3

Verdict: ACCEPTED

input
`500000 389924 57822 57822 217726 57822 139251 389924 399958 ...` view save

correct output
`13000624 8` view save

user output
`13000624 8` view save

Test 50

Group: 3

Verdict: ACCEPTED

input
`500000 118786 47756 47756 169958 118786 446268 47756 148195 ...` view save

correct output
`14000392 7` view save

user output
`14000392 7` view save

Test 51

Group: 3

Verdict: ACCEPTED

input
`500000 129573 222254 222254 126962 222254 118174 126962 228147 ...` view save

correct output
`13250477 3` view save

user output
`13250477 3` view save

Test 52

Group: 3

Verdict: ACCEPTED

input
`500000 161686 403260 161686 255571 161686 38129 161686 471358 ...` view save

correct output
`13000260 8` view save

user output
`13000260 8` view save

Test 53

Group: 3

Verdict: ACCEPTED

input
`500000 211000 360323 211000 25161 25161 410825 25161 228266 ...` view save

correct output
`15625250001 2` view save

user output
`15625250001 2` view save

Test 54

Group: 3

Verdict: ACCEPTED

input
`500000 229975 245878 229975 381069 381069 235752 381069 281659 ...` view save

correct output
`15625250001 2` view save

user output
`15625250001 2` view save

Test 55

Group: 3

Verdict: ACCEPTED

input
`500000 339362 207756 339362 329523 329523 104875 329523 406705 ...` view save

correct output
`15625250001 2` view save

user output
`15625250001 2` view save

Test 56

Group: 3

Verdict: ACCEPTED

input
`500000 177180 20224 177180 489549 489549 272251 489549 366798 ...` view save

correct output
`15625250001 2` view save

user output
`15625250001 2` view save

Test 57

Group: 3

Verdict: ACCEPTED

input
`500000 441050 365574 365574 260480 260480 489676 489676 475065 ...` view save

correct output
`46874937499 1` view save

user output
`46874937499 1` view save

Test 58

Group: 3

Verdict: ACCEPTED

input
`500000 441371 336553 336553 486568 486568 295839 295839 244926 ...` view save

correct output
`46874937499 1` view save

user output
`46874937499 1` view save

Test 59

Group: 3

Verdict: ACCEPTED

input
`500000 140194 178993 178993 120975 120975 81556 81556 124409 ...` view save

correct output
`46874937499 1` view save

user output
`46874937499 1` view save

Test 60

Group: 3

Verdict: ACCEPTED

input
`500000 476177 228555 228555 180476 180476 183974 183974 333290 ...` view save

correct output
`46874937499 1` view save

user output
`46874937499 1` view save

Test 61

Group: 3

Verdict: RUNTIME ERROR

input
`500000 470750 387879 417836 311762 342966 141634 406354 25179 ...` view save

correct output
`0 1` view save

user output
(empty)

Test 62

Group: 3

Verdict: RUNTIME ERROR

input
`499999 494831 301936 134173 372968 341642 209941 69019 60029 ...` view save

correct output
`0 1` view save

user output
(empty)

Test 63

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`499996 458465 327411 334721 342076 281173 482634 174786 302877 ...` view save

correct output
`19999600002 10` view save

user output
(empty)

Test 64

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`499991 469217 60234 337422 32098 391126 410047 250380 490453 ...` view save

correct output
`4999800002 45` view save

user output
(empty)

Test 65

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`499981 86341 52816 87685 124628 264008 93843 215407 204482 ...` view save

correct output
`1249900002 190` view save

user output
(empty)

Test 66

Group: 3

Verdict: ACCEPTED

input
`499951 173074 102553 4605 467972 179848 239784 41864 483920 ...` view save

correct output
`199960002 1225` view save

user output
`199960002 1225` view save

Test 67

Group: 3

Verdict: ACCEPTED

input
`499901 331534 159654 354263 417447 456398 336456 145925 93463 ...` view save

correct output
`49980002 4950` view save

user output
`49980002 4950` view save

Test 68

Group: 3

Verdict: ACCEPTED

input
`499801 316655 31406 375271 253377 207046 406296 261469 73474 ...` view save

correct output
`12490002 19900` view save

user output
`12490002 19900` view save

Test 69

Group: 3

Verdict: ACCEPTED

input
`499501 181530 1562 425296 130234 77519 429847 246899 62810 ...` view save

correct output
`1996002 124750` view save

user output
`1996002 124750` view save

Test 70

Group: 3

Verdict: ACCEPTED

input
`499001 119240 366053 80890 350931 299626 85851 452737 458125 ...` view save

correct output
`498002 499500` view save

user output
`498002 499500` view save

Test 71

Group: 3

Verdict: ACCEPTED

input
`497752 249959 43805 53866 407731 480579 76517 310033 271411 ...` view save

correct output
`124002 1997001` view save

user output
`124002 1997001` view save

Test 72

Group: 3

Verdict: ACCEPTED

input
`499801 311 302621 77322 218171 439178 122797 52421 371940 ...` view save

correct output
`80000 3121251` view save

user output
`80000 3121251` view save

Test 73

Group: 3

Verdict: ACCEPTED

input
`499951 15992 79636 154669 481782 18867 429430 314460 363528 ...` view save

correct output
`5000 49985001` view save

user output
`5000 49985001` view save

Test 74

Group: 3

Verdict: ACCEPTED

input
`499976 119557 332930 223497 192866 12074 112412 294767 451558 ...` view save

correct output
`1250 199970001` view save

user output
`1250 199970001` view save

Test 75

Group: 3

Verdict: ACCEPTED

input
`499991 420903 56414 2049 265308 289486 285688 134149 205864 ...` view save

correct output
`200 1249925001` view save

user output
`200 1249925001` view save

Test 76

Group: 3

Verdict: ACCEPTED

input
`499996 470165 235699 439599 455312 471414 301440 133301 186718 ...` view save

correct output
`50 4999850001` view save

user output
`50 4999850001` view save

Test 77

Group: 3

Verdict: ACCEPTED

input
`499999 354863 105878 6441 294653 154672 62081 62081 336952 ...` view save

correct output
`8 31249625001` view save

user output
`8 31249625001` view save

Test 78

Group: 3

Verdict: ACCEPTED

input
`500000 465618 25628 465618 443811 320366 465618 465618 382392 ...` view save

correct output
`2 124999250001` view save

user output
`2 124999250001` view save

IZhO 2017, day 2

Hard route

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

Test 73

Test 74

Test 75

Test 76